<!DOCTYPE html>
<html lang="zh-CN">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>408 | 月藤的博客</title>
    <meta name="generator" content="VuePress 1.8.0">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/KaTeX/0.7.1/katex.min.css">
    <link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/github-markdown-css/2.10.0/github-markdown.min.css">
    <meta name="description" content="简单的介绍">
    
    <link rel="preload" href="/assets/css/0.styles.a2e941e0.css" as="style"><link rel="preload" href="/assets/js/app.c7d9ff18.js" as="script"><link rel="preload" href="/assets/js/2.cd56dec9.js" as="script"><link rel="preload" href="/assets/js/8.04726c3a.js" as="script"><link rel="prefetch" href="/assets/js/10.21f484f8.js"><link rel="prefetch" href="/assets/js/11.5e166696.js"><link rel="prefetch" href="/assets/js/12.c56c19a2.js"><link rel="prefetch" href="/assets/js/13.3e31b609.js"><link rel="prefetch" href="/assets/js/14.3db3e5e6.js"><link rel="prefetch" href="/assets/js/15.cc75d7c3.js"><link rel="prefetch" href="/assets/js/16.5546d343.js"><link rel="prefetch" href="/assets/js/17.69b8a0f2.js"><link rel="prefetch" href="/assets/js/18.271396c8.js"><link rel="prefetch" href="/assets/js/19.bd4b0386.js"><link rel="prefetch" href="/assets/js/20.4a48d936.js"><link rel="prefetch" href="/assets/js/21.23862f34.js"><link rel="prefetch" href="/assets/js/22.95b3bd0a.js"><link rel="prefetch" href="/assets/js/23.d7c85d8e.js"><link rel="prefetch" href="/assets/js/24.c6d6dd3c.js"><link rel="prefetch" href="/assets/js/25.bb664de8.js"><link rel="prefetch" href="/assets/js/26.619789c7.js"><link rel="prefetch" href="/assets/js/27.54beb19d.js"><link rel="prefetch" href="/assets/js/28.8d77923a.js"><link rel="prefetch" href="/assets/js/29.7a771891.js"><link rel="prefetch" href="/assets/js/3.a0dd59cc.js"><link rel="prefetch" href="/assets/js/30.73e03cd7.js"><link rel="prefetch" href="/assets/js/31.a9a1ae37.js"><link rel="prefetch" href="/assets/js/32.66082a76.js"><link rel="prefetch" href="/assets/js/33.73a91496.js"><link rel="prefetch" href="/assets/js/34.da867ae2.js"><link rel="prefetch" href="/assets/js/35.6fac5ae2.js"><link rel="prefetch" href="/assets/js/36.0d6f5d22.js"><link rel="prefetch" href="/assets/js/37.c16a4955.js"><link rel="prefetch" href="/assets/js/38.3391e103.js"><link rel="prefetch" href="/assets/js/39.2e00541f.js"><link rel="prefetch" href="/assets/js/4.7f4b5eea.js"><link rel="prefetch" href="/assets/js/40.22b54e67.js"><link rel="prefetch" href="/assets/js/41.ea3ea4f8.js"><link rel="prefetch" href="/assets/js/42.3ae1db24.js"><link rel="prefetch" href="/assets/js/43.ecd8c202.js"><link rel="prefetch" href="/assets/js/44.f7609015.js"><link rel="prefetch" href="/assets/js/45.0db6f0b1.js"><link rel="prefetch" href="/assets/js/46.e28c1031.js"><link rel="prefetch" href="/assets/js/47.32d7164d.js"><link rel="prefetch" href="/assets/js/48.3aeaffda.js"><link rel="prefetch" href="/assets/js/49.33dab1c0.js"><link rel="prefetch" href="/assets/js/5.80c2b38b.js"><link rel="prefetch" href="/assets/js/50.6e41bca8.js"><link rel="prefetch" href="/assets/js/51.37e89a7c.js"><link rel="prefetch" href="/assets/js/52.e60e1d45.js"><link rel="prefetch" href="/assets/js/53.7a9c00ba.js"><link rel="prefetch" href="/assets/js/54.a214a30e.js"><link rel="prefetch" href="/assets/js/6.133fd621.js"><link rel="prefetch" href="/assets/js/7.79403511.js"><link rel="prefetch" href="/assets/js/9.a86daf82.js">
    <link rel="stylesheet" href="/assets/css/0.styles.a2e941e0.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">月藤的博客</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/考研专区/408总结.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><div class="avatar"><img src="/assets/img/avatar.2b77755b.png" alt srcset></div> <div style="z-index: 999"><iframe frameborder="no" border="0" marginwidth="0" marginheight="0" width="298" height="52" src="//music.163.com/outchain/player?type=2&id=28283137&auto=1&height=32"></iframe></div> <nav class="nav-links"><div class="nav-item"><a href="https://ziphold.gitee.io/blog/#/" target="_blank" rel="noopener noreferrer" class="nav-link external">
  旧博客（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><a href="https://rattonlzh.github.io/homepage/homepage.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  常用网址导航（停止更新）
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="Select language" class="dropdown-title"><span class="title">Languages</span> <span class="arrow down"></span></button> <button type="button" aria-label="Select language" class="mobile-dropdown-title"><span class="title">Languages</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/考研专区/408总结.html" class="nav-link">
  zh-CN
</a></li><li class="dropdown-item"><!----> <a href="/en/" class="nav-link">
  en-US
</a></li></ul></div></div> <!----></nav>  <ul class="sidebar-links"><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>随便说说</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>知识点总结</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading open"><span>考研专区</span> <span class="arrow down"></span></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/考研专区/2021考研政治总结.html" class="sidebar-link">2021考研政治总结</a></li><li><a href="/考研专区/408总结.html" class="active sidebar-link">408</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/考研专区/408总结.html#_408" class="sidebar-link">408</a></li></ul></li><li><a href="/考研专区/关键算法题解转载.html" class="sidebar-link">关键算法题解转载</a></li><li><a href="/考研专区/数学二总结.html" class="sidebar-link">数学二</a></li><li><a href="/考研专区/英语词组搭配.html" class="sidebar-link">英语</a></li></ul></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>读书笔记</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>开发资料</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>配置记录</span> <span class="arrow right"></span></p> <!----></section></li><li><section class="sidebar-group collapsable depth-0"><p class="sidebar-heading"><span>思维导图</span> <span class="arrow right"></span></p> <!----></section></li><li><a href="/friend_link.html" class="sidebar-link">友情链接</a></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h2 id="_408"><a href="#_408" class="header-anchor">#</a> 408</h2> <h3 id="b树"><a href="#b树" class="header-anchor">#</a> B树</h3> <p>keyword： 关键字，枝结点，叶结点，阶</p> <p>关键字：排序码</p> <p>枝结点：除了根节点的非叶子结点</p> <p>叶结点：无后继子结点的结点</p> <p>阶：一个结点最多能拥有的孩子结点数</p> <p>性质</p> <p>对于M阶B树，</p> <ul><li>一个结点的关键字个数不超过M-1</li> <li>一个结点的关键字个数不少于 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>⌈</mo><mi>M</mi><mi mathvariant="normal">/</mi><mn>2</mn><mo>⌉</mo><mo>−</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">\lceil M/2 \rceil -1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">⌈</span><span class="mord mathit" style="margin-right:0.10903em;">M</span><span class="mord mathrm">/</span><span class="mord mathrm">2</span><span class="mclose">⌉</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span></li> <li>所有叶结点在同一层</li></ul> <h3 id="海明码"><a href="#海明码" class="header-anchor">#</a> 海明码</h3> <p>传送门：[<a href="https://www.cnblogs.com/lesroad/p/8688634.html" target="_blank" rel="noopener noreferrer">【海明码】（容易看懂）<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>](https://www.cnblogs.com/lesroad/p/8688634.html)</p> <p>（PS）传送门的博客的校验位是从高位到低位排的，实际使用应从低位向高位排</p> <h3 id="关键点"><a href="#关键点" class="header-anchor">#</a> 关键点</h3> <ul><li>k个校验位，n个信息位，需保证 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mn>2</mn><mrow><mi>k</mi></mrow></msup><mo>−</mo><mn>1</mn><mo>≥</mo><mi>n</mi><mo>+</mo><mi>k</mi></mrow><annotation encoding="application/x-tex">2^{k}-1 \ge n+k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.849108em;"></span><span class="strut bottom" style="height:0.985078em;vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathrm">2</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mrel">≥</span><span class="mord mathit">n</span><span class="mbin">+</span><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span></span></li> <li>第k个校验位在第 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mn>2</mn><mi>k</mi></msup></mrow><annotation encoding="application/x-tex">2^k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.849108em;"></span><span class="strut bottom" style="height:0.849108em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathrm">2</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>号位置，记为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">x_k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span></li> <li>假设出错时只有一个错误位</li> <li><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>x</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">x_k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">x</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>取值需要满足使所有位置编号（按二进制编号）第k位为1的位的异或结果为0（相当于偶校验）</li> <li>检验过程：所有位置编号（按二进制编号）第k位为1的位进行异或得到 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>c</mi><mi>k</mi></msub></mrow><annotation encoding="application/x-tex">c_k</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.58056em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>, <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>c</mi><mi>k</mi></msub><msub><mi>c</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>⋯</mo><msub><mi>c</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">c_kc_{k-1}\cdots c_1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.638891em;vertical-align:-0.208331em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="minner">⋯</span><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>为校验码，取值表示错误发生的位的位置编号是  <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>c</mi><mi>k</mi></msub><msub><mi>c</mi><mrow><mi>k</mi><mo>−</mo><mn>1</mn></mrow></msub><mo>⋯</mo><msub><mi>c</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">c_kc_{k-1}\cdots c_1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.638891em;vertical-align:-0.208331em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit" style="margin-right:0.03148em;">k</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="minner">⋯</span><span class="mord"><span class="mord mathit">c</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span></li></ul> <h3 id="_408解题技巧"><a href="#_408解题技巧" class="header-anchor">#</a> 408解题技巧</h3> <ol><li><p>甘特图：解决多道程序执行时间问题</p></li> <li><p>时空图：计算流水线的加速比、效率、指令执行速度等</p></li> <li><p>分配矩阵需求矩阵、工作向量：用银行家算法判断是否是安全序列</p></li> <li><p>给出页面访问序列和可分配的页数n，且初始页表已满，求LRU的缺页次数的手工算法：从左到右扫描序列，找到一个缺页，从缺页位置往左扫描，遇到的元素在页表中排除，当页表中只剩下一个元素，此元素就是要被淘汰的页号，将该元素换出，缺页换入，继续在原来的缺页位置往右扫描直到扫描完毕</p></li> <li><p>在研究各种缓冲技术的每块数据的处理时间时，有一个技巧：假设一种初始状态，然后</p> <p>计算下一次到达相同状态时所需要的时间，就是处理一块数据所需要的时间。在单缓冲</p> <p>中，这种初始状态为：工作区是满的，缓冲区是空的。如题目没有明确说明，一般认为</p> <p>缓冲区的大小和工作区的大小相等。</p></li> <li><p>C是cpu处理数据时间，M是从缓存区传送到主存工作区时间，T是从外设传送到缓存区的时间，则单缓冲区处理一块数据用时（处理完第i+1块与处理完第i块的时间间隔）=max(C, T)+M，双缓冲区处理一块数据用时= max(C+M, T);</p></li></ol> <h3 id="定义"><a href="#定义" class="header-anchor">#</a> 定义</h3> <ul><li><p><strong>进程特征</strong></p></li> <li><ul><li>**动态性：**它由创建而产生，由调度而执行，由撤销而消亡</li> <li><strong>程序是指令集是静态的，进程是动态的</strong></li> <li><strong>并发性：<strong>多个进程实体在</strong>一段时间</strong>内同时进行</li> <li><strong>独立性：<strong>进程实体是独立运行、独立分配资源和独立接受调度的</strong>基本单位</strong></li> <li><strong>异步性：<strong>各进程</strong>独立、异步</strong>（速度不一致）地运行（这也是并发进程需要引入同步机制的原因）</li></ul></li></ul> <p><strong>多道程序的基本特征</strong>：制约性、间断性、共享性（注意没有顺序性）</p> <p><strong>实时系统</strong>：安全可靠，及时响应，资源利用率低</p> <p><strong>电算化</strong>：数据处理，与科学计算无关</p> <p><strong>临界区</strong>：每个进程中访问临界资源的<em>那段代码</em>称为临界区</p> <p><strong>处理器的效率</strong>：获得处理器的时间占总运行时间的比例</p> <p><strong>流水线吞吐率</strong>：单位时间内流水线所完成的任务数量或输出结果的数量</p> <p><strong>流水线加速比</strong>：使用顺序处理方式处理一批任务所用的时间与按流水处理方式处理同一 批任务所用的时间之比</p> <p><strong>流水线效率</strong>：即流水线设备的利用率，指流水线中的设备实际使用时间与整个运行时间（流水线运行时间乘以流水线级数）的比值=时空图上任务所占面积/总面积</p> <p><strong>简单回路</strong>：除第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路</p> <p><strong>高级调度</strong>：作业调度；中级调度：内存调度；低级调度：进程调度</p> <p><strong>周转时间</strong> = 作业完成时间 - 作业提交时间</p> <p><strong>强化碰撞</strong>=CSMA/CD协议中发送数据的站检测到了冲突后，除了立即停止发送外，还要发送32比特或48比特的人为干扰信号，以便让所有用户都知道现在已经快发生了碰撞</p> <p><em>带权周转时间</em>：\frac{周转时间}{运行时间}</p> <p><strong>响应比</strong> = \frac{等待时间+要求服务时间}{要求服务时间}（其实就相当于带权周转时间）</p> <p><strong>操作系统最基本的两个特性</strong>：并发和共享</p> <p><strong>抖动</strong>：刚被换出的页面又被换入；抖动的主要原因是频繁访问的页数高数可用的物理页数</p> <p><strong>工作集</strong>：某段时间间隔内，进程要访问的页面集合，要时间t和工作集大小窗口 $\Delta $确定：在访问序列中从t时刻前 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">Δ</mi></mrow><annotation encoding="application/x-tex">\Delta</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">Δ</span></span></span></span> 个元素，将不再工作集的页号添加到工作集中</p> <h3 id="faq"><a href="#faq" class="header-anchor">#</a> FAQ</h3> <p><strong>为什么要区分用户态和核心态， 两者切换的时机是什么？</strong></p> <p>主要目的是保护操作系统，用户态-&gt;核心态：中断；核心态-&gt;用户态：中断返回</p> <p><strong>为什么直到出现中断和通道技术后，多道技术才变得有用？</strong></p> <p>中断和通道技术使外部设备和CPU真正并行工作称为可能</p> <p><strong>程序和进程的区别是什么</strong></p> <p>程序是静态的指令集合，只占据磁盘空间，进程是程序的动态执行过程，需要分配CPU，内存等资源</p> <p><strong>进程和程序之间可以形成一对一 什么情况下会形成这样的关系。 一对多、多对一、多对多的关系，请分别举例说明在什么情况下会形成这样的关系</strong></p> <p>执行一条命令或运行一个应用程序时，进程和程序之间形成一对一的关系。进程在执行过程中可以<em>加载执行不同的应用程序</em>，从而形成一对多的关系；以<em>不同的参数或数据</em>多次执行同一个 应用程序时，形成多对一的关系；并发地执行不同的应用程序时，形成多对多的关系。</p> <p><strong>父进程创建子进程和主程序调用子程序有何不同？</strong></p> <p>父进程创建子进程后，父进程与子进程同时执行（并发）。主程序调用子程序后，主程序暂停在调用点，子程序开始执行，直到子程序返回，主程序才开始执行。</p> <p><strong>为什么进程之间的通信必须借助于操作系统内核功能？简单说明进程通信的几种主要方式。</strong></p> <p>每个进程有自己独立的地址空间。在操作系统和硬件的地址保护机制下，进程<em>无法</em>访问其他进程的<em>地址空间</em>，所以必须借助于操作系统的系统调用函数实现进程之间的通信。进程通信的主要有共享内存区、消息传递、管道、共享文件</p> <p><strong>什么是多线程？多线程与多任务有什么区别？</strong></p> <p>多线程是指在一个程序中可以定义多个线程并同时运行它们，每个线程可以执行不同的任务。 多线程与多任务的区别：多任务是针对<em>操作系统</em>而言的，代表操作系统可以<em>同时</em>执行的程序 个数；多线程是针对一个<em>程序</em>而言的，代表一个程序可以同时执行的线程个数，而每个线程可以 完成不同的任务。</p> <p><strong>为什么引入进程的概念？</strong></p> <p>并发具有间断性和不可再现性，为了更好的描述和控制并发程序的执行，便引入了进程</p> <p><strong>若系统中没有运行进程，是否一定没有就绪进程？为什么？ 若系统中既没有运行进程，又没有就绪进程，系统中是否就没有进程？为什么？ 在采用优先级进程调度时，运行进程是否一定是系统中优先级最高的进程？</strong></p> <p>是。若系统中未运行进程，则系统很快会选择一个就绪进程运行。只有就绪队列中无进 程时，CPU才可能处于空闲状态； 不一定。因为系统中的所有进程可能都处于等待态，可能处于死锁状态，也有可能因为 等待的事件未发生而进入循环等待态。 不一定。因为高优先级的进程有可能正处在等待队列中，进程调度会从就绪队列中选择 一个进程占用CPU，这个被选中的进程可能优先级较低。</p> <p><strong>支持多进程的并发执行，系统必须建立哪些关于进程的数据结构？</strong></p> <p>为支持多进程的并发执行，系统为每个进程建立了一个数据结构：进程控制块（PCB）， 用于进程的管理和控制。PCB中记录了有关进程的一些描述信息和控制信息，包括进程 标识符、进程当前的状态、优先级、进程放弃CPU时的现场信息，以及指示组成进程的 程序和数据在存储器中存放位置的信息、资源使用信息、进程各种队列的连接指针和反 映进程之间的隶属关系的信息等。</p> <p>**为支持进程状态的变迁，系统至少应提供哪些进程控制原语？ **</p> <p>创建新进程原语、阻塞进程原语、唤醒进程原语、终止进程原语等操作。</p> <p><strong>执行每个进程控制原语时，进程状态发生什么变化？相应的数据结构发生什么变化？</strong></p> <p>进程创建原语：从PCB集合中申请一个空白的PCB，将调用者参数（如进程外部标识符、 初始CPU状态、进程优先数、初始内存及申请资源清单等）添入该PCB，设置记账数据。 置新进程为“就绪”态。</p> <p>终止进程原语：用于终止完成的进程，回收其所占资源。包括消去其资源描述块，消去 进程的PCB。</p> <p>阻塞原语：进程从运行态变为阻塞态。进程被插入等待队列，同时修改PCB中 相应的表项，如进程状态和等待队列指针等。</p> <p>唤醒原语：将进程从阻塞态变为就绪态。进程从阻塞队列中移出，插入就绪队列，等待调度，同时修改PCB中相应的表项，如进程状态等。</p> <p><strong>何谓管程？管程由几部分组成？说明引入管程的必要性。</strong></p> <p>封装了共享数据结构和对该数据结构进行操作的一组过程的资源管理程序。由3个部分组成，如下：</p> <ul><li>局部于管程内部的共享变量说明</li> <li>该数据结构进行操作的一组过程</li> <li>对局部于管程的数据设置初始值的语句</li></ul> <p>管程的引入是为了解决临界区分散所带来的的管理和控制问题，管程一次只能有一个进程进入管程内，既便于系统管理共享资源，又能保证互斥</p> <p><strong>死锁定理是什么</strong></p> <p>S为死锁的条件是当且仅当S的状态的资源分配图是不可完全简化的</p> <p><strong>死锁解除的方法有什么</strong></p> <ol><li>剥夺资源</li> <li>撤销进程</li> <li>进程回退</li></ol> <p><strong>死锁的预防和死锁的避免有什么区别</strong></p> <p>预防是指设置限制条件，破坏死锁的必要条件</p> <p>避免是在动态分配资源的过程中，避免进入不安全状态，从而避免死锁</p> <p><strong>死锁的四个必要条件是什么，无法破坏的是哪个条件</strong></p> <ol><li>互斥（无法被破坏）</li> <li>占有并保持</li> <li>循环等待</li> <li>不剥夺，即非抢占式分配</li></ol> <p><strong>银行家算法、检测死锁、资源预分配，对这解决死锁的3种方法，按照并发性从大到小排序</strong></p> <p>检测死锁&gt;银行家算法&gt;资源预分配</p> <p><strong>某银行计算机系统要实现一个电子转账系统，基本业务流程是：首先对转出方和转入方 的账户进行加锁，然后进行转账业务，最后对转出方和转入方的账户进行解锁。若不采取任何措施，系统会不会发生死锁？为啥？请设计一个能够避免死锁的方法</strong></p> <p>当A向B转账时，先对A加锁，再申请对B加锁，与此同时，B向A转账，先对B加锁，再申请对A加锁，就会导致死锁；为了解决死锁问题，使用资源顺序分配法，对所有账号编号，用户转账只能按照编号从小到大的顺序加锁</p> <p><strong>为确保进程正确进行，应采用怎样的分配策略，列出所有可能的方法</strong></p> <ol><li>采用静态分配</li> <li>采用按序分配</li> <li>采用银行家算法</li></ol> <p><strong>死锁和饥饿的区别</strong></p> <p>死锁是相关进程都处于阻塞状态，无法继续推进，饥饿是由于分配策略的不公平，尽管不是所有进程都处于阻塞状态，但存在某个进程长期被阻塞；当饥饿到一定程度，进程的任务即使完成也失去了实际意义，这个现象称为进程被饿死</p> <p><strong>什么是可重入代码，可重入程序</strong></p> <p>不能被修改的代码被称为<em>可重入代码</em>或纯代码；可重入代码不属于临界资源，可以被共享</p> <p>可重入程序是指该程序被某进程调用，但还未结束，又被另一个进程调用。</p> <p>可重入程序是通过减少对换信息量来改善系统响应时间的。</p> <p>可重入程序主要通过共享来使用同一块存储空间的，或者通过动态链接的方式将所需的程序段映射到相关进程中去，其最大的优点是减少了对程序段的调入调出。由此来减少对换信息量。</p> <p><strong>覆盖技术与虚拟存储技术有何本质上的不同？交换技术与虚拟存储技术中使用的调入/调 出技术有何相同与不同之处？</strong></p> <p>覆盖程序段的大小受主存容量限制，且覆盖段有程序员设计，各个覆盖段不能有直接联系或相互交叉访问；</p> <p>交换技术和虚拟存储技术的调入调出技术都是内存与外存交换信息；交换技术调入调出整个进程，后者调入调出的是段或页</p> <p><strong>什么是临界资源、临界区</strong></p> <p>多个进程对某个资源的访问必须互斥进行，这个资源就称为临界资源</p> <p>进程中访问临界资源的一段代码</p> <p><strong>为什么要进行内存管理</strong></p> <p>多道程序技术引入后，进程共享内存，如果不加管理，容易导致内存数据混乱，导致程序出错</p> <p><strong>什么是外部碎片，内部碎片</strong></p> <p>外部碎片是指还没有被分配出去（不属于任何进程），但由于太小了无法分配给申请内存空间的新进程的内存空闲区域；</p> <p>内部碎片是指已分配给进程但是没有被使用的内存区域</p> <p><strong>可变分区分配是什么</strong></p> <p>可变分区是多道可变连续分配</p> <p><strong>多级页表的优缺点</strong></p> <p>解决了逻辑空间过大时页表长度大大增加的问题；缺点是一次访存可能需要多次访问内存甚至磁盘</p> <p><strong>动态重定位、静态重定位的特点</strong></p> <p>静态重定位要求作业装入内存时分配全部的内存空间，若没有足够的内存，则不能装入该作业；一旦装入内存，运行期间就不能再内存中移动，也不能再申请内存空间</p> <p>动态重定位可以把程序分配到不连续的存储区中；运行之前可以只装入部分代码即可运行；运行期间，根据需要动态分配内存，便于段的共享，可以向用户提供比存储空间大得多的地址空间</p> <p><strong>什么是虚拟存储器</strong></p> <p>操作系统通过某些技术使得看上去提供了比实际内存大得多的存储器，这个存储器就叫虚拟存储器。虚拟存储器有3个特征——</p> <ol><li>多次性（作业无需全部调入内存，可以被分成多次调入内存）</li> <li>对换性（作业无需常驻内存，运行一部分换入和换出）</li> <li>虚拟性（从逻辑上扩充容量）</li></ol> <p><strong>什么是Belady异常</strong></p> <p>随着分配到的物理块数增大而页故障数不减反增的现象称为Belady异常，只有FIFO算法会导致Belady现象</p> <p><strong>介绍几种页面置换算法</strong></p> <ol><li>FIFO：优先淘汰最早进入内存的页面，没有考虑局部性原理，会出现Belady异常</li> <li>OPT：淘汰将来最长时间未被访问的页面，实践上无法实现</li> <li>LRU:  淘汰最长时间未被访问的页面，每个页面需要一个访问字段，记录自上次被访问以来经历的时间</li> <li>NRU(简单CLOCK或最近未使用算法): 自上次换入的位置开始循环扫描帧集合，如果访问位为1，则修改位0；如果访问位为0，则将该帧替换</li> <li>Advance CLOCK：在访问位的基础上增设修改位；循环扫描帧集合，第一趟扫描找访问位和修改位为0的帧进行替换；第二趟扫描找访问位0，修改位为1的帧替换，对于跳过的帧，将访问位修改为0；如果前两趟都失败，则重复一次前两趟扫描，必能找到需要替换的帧</li></ol> <p><strong>什么是驻留集，常见的页面分配策略、调页策略是什么，从何处调入页面</strong></p> <p>驻留集是指给进程分配的物理页框的集合，驻留集的常见分配策略如下：</p> <ol><li>固定分配局部替换：驻留集的大小和位置固定，只能从本进程的页面换出</li> <li>可变分配全局替换：系统维护一个空闲物理块队列，发生缺页时，可以使驻留集变大，可以选择其他进程的一页换出</li> <li>可变分配局部替换：频繁缺页使驻留集变大，缺页率低时使驻留集变小；只能从本进程的页面选择一页换出</li></ol> <p>没有固定分配全局置换：因为全局替换把其他进程的不用的页面置换成本进程的页面，违背了固定分配一个分区只装入一个作业的原则</p> <p><strong>什么是固定分配</strong></p> <p>将内存用户空间划分为多个固定大小的区域，在<strong>每个分区中只装入一个作业</strong>。</p> <p>调页策略有两种，一般同时使用，如下：</p> <ol><li>预调页策略：运行前由程序员指出先调入哪些页</li> <li>请求调页策略：运行期间调入，一次调入一页</li></ol> <p>从何处调入页面的分3种情况：</p> <ol><li>对换区空间充足：运行前将进程相关文件从文件区复制到对换区，从对换区进行调入页</li> <li>对换空间不足：可能被修改的页换出到对换区，不会被修改的页不需要换出，允许被其他页覆盖</li> <li>UNIX方式：从未运行的页面从文件区调入；运行过的被换出到对换区，下次调入时从对换区中调入</li></ol> <p><strong>对换区和文件区的区别</strong></p> <p>对换区是连续分配，文件区是离散分配，因此对换区的磁盘I/O速度比文件区快</p> <p><strong>文件的6个基本操作</strong></p> <ol><li>创建文件</li> <li>写文件</li> <li>读文件</li> <li>文件重定位</li> <li>删除文件</li> <li>截断文件</li></ol> <p><strong>文件分配方式有哪些，空闲盘块的管理方式有哪些</strong></p> <p>文件盘块分配方式如下：</p> <ol><li>连续分配：目录项记录了文件名、起始块地址和文件长度</li> <li>链式分配：
<ol><li>隐式链式分配：目录项记录了文件名、初始块和最后一个块的指针</li> <li>显式链式分配：在这个磁盘中仅设置一张文件分配表FAT，每个FAT表项记录了盘块号A和next盘块号B（B=-1表示A是文件的最后一个块的盘块号，-2或者其它负数表示盘块A是空闲的），有点像静态链表，在系统启动时就会被读入内存，提高了检索速度，减少了访问磁盘的次数；目录项记录了文件名和初始盘块号</li></ol></li> <li>索引分配：有一个索引表，给文件分配盘块时给文件分配一个索引块，将分配的盘块的地址写入到索引块中；目录项记录了文件名和索引块的块号</li></ol> <p>空闲盘块的管理有一下方式</p> <ol><li>空闲表法</li> <li>空闲链表法</li> <li>位示图法</li> <li>成组链接法：一个顺序空闲扇区（成组链块）记录n个连续空闲扇区的地址和另一个顺序空闲扇区的地址；第一个成组链块一般放在卷头位置，在UNIX系统中称为超级块，对卷的文件操作前，需要读入内存</li></ol> <p><strong>空白磁盘格式化包括哪些步骤</strong></p> <p>包括低级格式化、逻辑分区、逻辑格式化</p> <p>低级格式化（物理分区）指对磁盘分区，为每个扇区采用特别的数据结构包括校验码</p> <p>逻辑分区将磁盘分为由1个或多个柱面组成的逻辑分区，每个分区都可以作为一个独立的磁盘</p> <p>逻辑格式化指创建文件系统，将初始的文件系统数据结构存储到磁盘上。这些数据结构包括空闲和已分配的空间及一个初始为空的目录</p> <p><strong>设备分类有哪些</strong></p> <p>按信息交换的单位来分，可分为块设备和字符设备；</p> <ul><li>块设备是有结构设备、传输速率较高，可寻址，随机读写任何一块</li> <li>字符设备是无结构设备，传输单位是字符，传输速率低，不可寻址，在输入、输出中常采用中断驱动方式</li></ul> <h3 id="关键点-2"><a href="#关键点-2" class="header-anchor">#</a> 关键点</h3> <ol><li><p>看到端对端通信，应该选传输层；点对点通信，选数据链路层</p></li> <li><p>SPOOLing系统由预输入系统、井管理程序和缓输出程序，需要使用磁盘空间（输入井、输出井）和内存空间(输入、输出缓冲区)，不需要外围计算机的支持</p></li> <li><p>共享设备必须是可寻址和可随机访问的设备</p></li> <li><p>同一时间内允许多个进程同时访问称为并行；一段时间内允许多个进程同时进行访问称为并发</p></li> <li><p>扇区数据处理的时间主要影响传输时间而非旋转延迟时间；磁盘空闲空间的分配程序决定了文件是否连续分配，会影响旋转延迟时间</p></li> <li><p>提高单机资源利用率的关键技术是多道程序设计技术</p></li> <li><p>设备的独立性是指用户编程时使用的设备与实际使用的设备无关</p></li> <li><p>设备控制器用于实现设备控制功能的是I/O逻辑，用于传输信号的是接口</p></li> <li><p>为了方便上层软件的编制、设备控制器通常需要提供控制寄存器、状态寄存器和控制命令</p></li> <li><p>在一个文件卷中，目录区是存放FCB的空间；目录区和文件区是分离的</p></li> <li><p>动态重定位需要一个重定位寄存器</p></li> <li><p>设备的固有属性决定了设备的使用方式；设备独立性可以提高设备分配方式的灵活性和设备的利用率；设备安全性可以保证分配设备时不会导致永久阻塞</p></li> <li><p>字节多路通道用于连接大量低速、中速设备；通过时间片轮转共享主通道</p></li> <li><p>一个计算机系统配置了n台打印机和m台绘图机，需要提供的只是打印机和绘图机的设备驱动程序各1个</p></li> <li><p>通道是特殊的处理器，不属于软件</p></li> <li><p>所有设备的启动工作都由系统统一来做</p></li> <li><p>将系统的每一台设备按某种原则统一进行编号，编号作为区分硬件和设别设备的代号，这编号称为设备的<em>绝对号</em></p></li> <li><p>内存保护需要有操作系统和硬件机构<em>合作</em>完成，以保证进程空间不被非法访问</p></li> <li><p>形成逻辑地址的阶段是<em>链接</em>阶段，不是<em>编译</em>阶段</p></li> <li><p>物理地址= 块号*页面大小+页内偏移地址</p></li> <li><p>产生死锁的原因可归结为竞争资源、进程推进顺序非法</p></li> <li><p>资源分配图化简法属于死锁检测策略</p></li> <li><p>建立缓存区的目的是使高速设备和低速设备的通信经过缓存区，避免高速设备与低速设备的直接访问</p></li> <li><p>open操作根据文件名将目录项从外存复制到内存的文件打开表中，并返回一个文件指针， 用户通过该指针访问文件</p></li> <li><p>在存储管理中， 使用覆盖和交换的技术的目的是<em>节省主存空间</em>，不是实现主存共享</p></li> <li><p>使用交换技术时，若一个进程正在进行I/O操作，则不能换出内存，否则I/O数据区将被新换入的进程占用，导致错误；不过可以在操作系统开辟I/O缓冲区，将数据从外设输入或将数据输出到外设的I/O活动在系统缓冲区中进行，这时进程交换不受限制</p></li> <li><p>覆盖和交换技术的提出是为了解决内存不足的问题，即节省内存空间</p></li> <li><p>败者树是完全二叉树，用于对k个归并段进行归并，归并段的第一个数据是败者树的叶节点，分支节点保存败者的归并段序号</p></li> <li><p>VLAN可以隔离广播域和冲突域</p></li> <li><p>SDT(系统设备表)-&gt;DCT(设备控制表)-&gt;COCT（控制器控制表）-&gt;CHCT（通道控制表）</p></li> <li><p>缺页中断是内部中断，在执行期间而非执行完成产生和处理中断信号，一条指令执行期间可能有多次缺页中断</p></li> <li><p>请求分页方法是目前最常见的一种实现虚拟存储器的方法</p></li> <li><p>请求分页系统中的页表项结构如下</p> <table><thead><tr><th>页号</th> <th>物理块号</th> <th>状态位P</th> <th>访问字段A</th> <th>修改位</th> <th>外存地址</th></tr></thead> <tbody><tr><td></td> <td></td> <td></td> <td></td> <td></td> <td></td></tr></tbody></table></li> <li><p>分页存储管理的作业地址空间是一维的；分段存储管理的作业地址空间是二维的；因为分页的地址空间只需要页帧号，分段的地址空间不要段始址和段大小</p></li> <li><p>页表中被淘汰的页的物理页号称为换入的页的物理页号</p></li> <li><p>最先适应内存分配性能比最佳适应内存分配好，最先适应算法尽可能使用了低地址部分的空闲区域，留下了搞地质部分的大的空闲区，更可能满足进程的申请</p></li> <li><p>程序的动态链接与程序的逻辑结构有关，分段存储管理有利于动态链接</p></li> <li><p>段式存储管理便于编程、共享和保护、动态链接和增长；方便操作不是目的</p></li> <li><p>对主存储器的访问，以字节或字为单位</p></li> <li><p>文件分为流式文件和记录文件</p></li> <li><p>文件重定位就是文件寻址，定位到文件所在目录</p></li> <li><p>合适的页面大小是通过一定的计算取得的，不是越大越好，也不是越小越好</p></li> <li><p>对外存对换区的管理以提高换入、换出速度为<em>主要目标</em></p></li> <li><p>整个系统只需要设置一个重定位寄存器，切换程序执行时会重置重定位寄存器内容</p></li> <li><p>最佳k路归并树是k路哈弗曼树</p></li> <li><p>操作系统引入文件系统的目的是实现对文件的按名存取</p></li> <li><p>引入文件系统的目的是<em>实现对文件的按名存取</em></p></li> <li><p>补码减法运算的借位标志CF = C ^ 1. C是进位输出</p></li> <li><p>IEEE754以及x86 FPU的默认舍入模式是最近舍入：当有两个最接近的可表示的值时首选“偶数”值；向负无穷大（向下）；向正无穷大（向上）以及向0（截断）。</p></li> <li><p>区分是RISC还是CISC：如果指令的长度不一致，则一定是CISC</p></li> <li><p>页式管理或段式管理中，系统提供给用户的物理地址空间=总空间大小-页表或段表的长度</p></li> <li><p>可变分区、页式、段式都可以在运行过程中改变程序位置，属于动态重定位；固定分区方式，作业装入后位置不再改变，属于静态重定位</p></li> <li><p>信号量同步可以实现让权等待（因为引入了阻塞机制）；硬件方法（Swap和TestAndSet）和Peterson算法都不能实现让权等待</p></li> <li><p>索引文件由逻辑文件和索引表组成</p></li> <li><p>文件的逻辑结构是方便用户而设计的</p></li> <li><p>文件按逻辑结构可分为流文件和结构文件；结构文件可分为顺序文件、索引文件、索引顺序文件、直接hash文件</p></li> <li><p>请求分页存储管理，如果存放程序需要的页帧数减少，则缺页的次数也会减少</p></li> <li><p>让页表常驻内存可以加快虚实地址转换</p></li> <li><p>缺页不需要处理越界错，因为缺页不会导致越界错误</p></li> <li><p>虚拟存储器的最大容量是由计算机的地址结构决定的，与主存容量和外存容量没有必要的联系</p></li> <li><p>页表的页号位数由虚拟地址空间决定而非实地址空间</p></li> <li><p>管程的wait()操作直接阻塞进程，并将之插入阻塞队列中，而信号量同步的V操作需要根据信号量的值决定是否进入阻塞态</p></li> <li><p>段页式管理，通过段表找到页表始址，在页表中根据页号找到页帧号，最后形成物理地址</p></li> <li><p>一个进程，段表只有一个，页表可以有多个</p></li> <li><p>管程可以看做是对共享数据结构及其操作的封装，每次只能有一个进程调用管程，实现对共享数据的互斥访问</p></li> <li><p>信号量可以看成两类（非官方定义）：互斥信号量和资源信号量；同时使用两类信号量时，必须先P(资源信号量)再P(互斥信号量)， 否则如果一开始就资源不足，先P互斥就会导致死锁。先P资源后P互斥是确保资源充足再选择其运行，属于死锁避免；两个相邻V操作调换位置无影响，但P不行</p></li> <li><p>分时系统的时间片固定，因此用户数越多，响应时间越长</p></li> <li><p>引入多道程序技术的前提条件之一是系统具有中断技术</p></li> <li><p>抢占式分配策略可能导致饥饿</p></li> <li><p><code>while(TSL(&amp;lock));</code>语句不应该一直保持关中断的状态，若<code>TSL(&amp;lock)</code>一直为true，不再开中断，会导致系统终止</p></li> <li><p>中断向量是中断服务程序的入口，中断向量地址是入口<em>地址的地址</em></p></li> <li><p>时间片调度是绝对可抢占的，时间片一到，立马剥夺当前进程</p></li> <li><p>链路层的流量控制机制控制的是点对点之间的流量，TCP协议的流量控制针对的是端对端的流量</p></li> <li><p>CPU密集型相当于长作业，IO繁忙性相当于短作业（因为会频繁放弃CPU）</p></li> <li><p>系统DLL库的系统线程被不同的进程调用，依然是<em>相同</em>的线程</p></li> <li><p>IR, MDR, MAR，cache对所有用户透明，通用寄存器、PSW对所有用户可见，PC对汇编程序员可见，虚拟存储器对系统程序员可见</p></li> <li><p>全1ip地址表示整个TCP/IP网络的广播地址，又称<em>受限广播地址</em>实际使用，由于路由器对广播域的隔离，等效为本网络的广播地址</p></li> <li><p>DHCP客户机广播DHCP发现帧-&gt;DHCP服务器广播DHCP提供帧-&gt;DHCP客户机广播DHCP请求帧-&gt;DHCP服务器广播确认帧</p></li> <li><p>ipv4首部的协议字段占8位，17为UDP协议</p></li> <li><p>逻辑格式化不包括对磁盘进行分区</p></li> <li><p>实际上几乎不使用递归查询，因为对根域名服务器造成的负载过大</p></li> <li><p>注意区分旋转延迟时间和读取一个扇区的时间：前者是转速的倒数除以2，后者是转速的倒数除以扇区数</p></li> <li><p>进程失去封闭性，是指并发进程共享变量，执行结果与速度有关</p></li> <li><p>计算tcp首部校验和需要加上16字节的伪首部</p></li> <li><p>对同一个变量的一读一写或两个都为写，都是互斥关系</p></li> <li><p>tcp首部的窗口值（发送方的接收窗口） = 拥塞窗口和接收窗口取最小值</p></li> <li><p>tcp首部长度能被4整除</p></li> <li><p>HTTP非持久连接：每个图像，css等的传输都需要单独建立一个TCP连接；HTTP持久连接：服务器发送响应后继续保持这条连接（http1.1支持）</p></li> <li><p>持久连接非流水线：等待收到前一个响应后再发出下一个请求；持久连接流水线：客户每遇到一个对象引用，立即发出一个请求</p></li> <li><p>tcp连接建立后所有传送的报文段的ACK都必须置1</p></li> <li><p>DNS,TFTP,SNMP,RTP(实时传输协议)都用UDP</p></li> <li><p>0-1023是熟知端口号，1024-49151是登记端口号，49152-65535是临时端口号</p></li> <li><p>虚电路不需要预分配带宽</p></li> <li><p>能运行组播协议的路由器称为组播路由器</p></li> <li><p>BGP边界网关协议是应用层协议，基于TCP;RIP基于UDP;OSPF基于IP，属于网络层协议</p></li> <li><p>RIP 允许的最大跳数是15，16就是不可达</p></li> <li><p>引入虚存可以在内存中容纳更多并发程序执行</p></li> <li><p>第2次挥手是对第一次挥手的确认，但是FIN没有置为1，第3次挥手才FIN=1；如果服务器收到第一次挥手后，已经没有数据要发送，则跳过第二次挥手</p></li> <li><p>如果服务器收到关闭连接的报文段后没有额外数据要发送，则可以省略第2次挥手，此时释放连接只需要3次挥手</p></li> <li><p>需要互斥访问的是执行顺序不确定时会导致各自的执行结果不确定的操作</p></li> <li><p>每次收到报文，服务端重置保活计时器的计数（2小时定时），如果计时器到时还没有收到数据，则主动向客户端发送一个探测报文，以后每隔75秒发送一次，重复10次发送探测报文都没有收到确认，则认为客户端出现故障，服务端关闭这个连接</p></li> <li><p>交换用于不同进程，覆盖用于同一个进程</p></li> <li><p>交换技术用于中级调度即内存调度</p></li> <li><p>段页式存储管理属于内存非连续分配</p></li> <li><p><img src="/assets/img/image-20201221202701176.32773cd0.png" alt="image-20201221202701176"></p></li> <li><p>临近适应算法（next fit）就是循环首次适应算法，分配内存时从上次查找结束的位置开始继续查找</p></li> <li><p>动态分区就是不预先划分分区，而是进程装入内存时，根据进程的大小动态建立分区</p></li> <li><p>界地址寄存器比较的是逻辑地址</p></li> <li><p>一般页的大小为4KB，页表项大小为4B， 12位低地址作为页内偏移，高10位作为一级页表的页号，中间10位作为二级页表的页号</p></li> <li><p>段表包括段号、段长、段基址；段控制寄存器包含了段表始址和段表长度</p></li> <li><p>段表项地址=段表始址+段号x段表项长度</p></li> <li><p>页表项地址=页表始址+页号x页表项长度</p></li> <li><p>页表记录了页号到物理块号的映射；为了找到页表项，需要知道页表的始址和页号</p></li> <li><p>顶级页表只能占1个页面</p></li> <li><p>位示图从左到右、从上到下第i个bit表示第i个物理块的分配情况，分配内存时，找第一个为0并修改为1，表示分配该空闲块</p></li> <li><p>cache行大小为N字节，按字节偏移， 则块偏移为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>log</mi><mn>2</mn></msub><mi>N</mi></mrow><annotation encoding="application/x-tex">\log_2 N</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.9388799999999999em;vertical-align:-0.24444em;"></span><span class="base textstyle uncramped"><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="vlist"><span style="top:0.24444em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathit" style="margin-right:0.10903em;">N</span></span></span></span>；cache直接映射与一页映射</p></li> <li><p>对于使用组相联的TLB，虚拟页号的低位用作组号，高位用作TLB标记</p></li> <li><p>页表寄存器存放但是页表始址和页表长度</p></li> <li><p>快表又称相联存储器</p></li> <li><p>进程中的块称为页，内存中的块称为页帧或页框，外存中的块直接称为块</p></li> <li><p>像键盘输入等低速设备的操作一般都<em>不</em>需要并发</p></li> <li><p>进程申请<em>处理器</em>得不到满足变为就绪态，申请处理器<em>之外</em>的资源得不到满足变为阻塞态</p></li> <li><p>处理<em>外部</em>中断时，应由操作系统保存的是<em>通用寄存器</em>的内容而不是PC</p></li> <li><p>批处理：用户脱机使用计算机， 作业是成批处理的，程序内多道程序并发执行，交互能力差；分时让多个用户同时使用计算机，人机交互强，系统响应及时；实时能对控制对象作出及时反应，可靠性高，响应及时，资源利用率低</p></li> <li><p>节点数为n的完全二叉树的叶节点个数= <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>⌊</mo><mfrac><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><mrow><mn>2</mn></mrow></mfrac><mo>⌋</mo></mrow><annotation encoding="application/x-tex">\lfloor\frac{n+1}{2}\rfloor</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.845108em;"></span><span class="strut bottom" style="height:1.190108em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mopen">⌊</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">2</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit">n</span><span class="mbin">+</span><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌋</span></span></span></span></p></li> <li><p>负数的补码越大，绝对值越小，真值越大</p></li> <li><p>ROM和DRAM 的地址是分两次传输，一次传行地址，一次传列地址，所以地址线总数是 $\frac {\log_2 n}{2} $</p></li> <li><p>管程的signal操作与信号量机制的V操作不同，信号量机制的V操作一定会改变信号量：S=S+1，管程的signal操作是针对条件变量的，如果不存在因该条件而阻塞的进程，则signal操作不会有任何影响</p></li> <li><p>如果n个并发进程涉及相同变量A，则A的相关临界区有n个</p></li> <li><p>生产者和消费者之间的制约关系是同步+互斥（因为不能一边生产数据一边取走数据，所以包含了互斥）</p></li> <li><p>用户通过命令接口和函数调用来使用计算机</p></li> <li><p>信道利用率=发送时延/总时延</p></li> <li><p>不同的VLAN是不同的广播域</p></li> <li><p>1-持续CSMA信道一旦空闲，立即发送</p></li> <li><p>p-持续CSMA信道一旦空闲，以p的概率发送</p></li> <li><p>CSMA/CA（碰撞避免）解决隐蔽站问题（A在C的范围外，B在A和C范围内，则A无法检测到B会发生碰撞）</p></li> <li><p>运行tracert命令的主机收到的icmp报文是主机不可达</p></li> <li><p>TTL = 0或没有在规定时间内收到所有数据分片，发送时间超过ICMP报文</p></li> <li><p>ping发送回送请求ICMP报文</p></li> <li><p>多个连在同一个集线器上的PC中两个PC同时发送报文发生了碰撞，所有的PC都能检测到这个碰撞</p></li> <li><p>802.11无线局域网的MAC层标准定义了两种媒体接入控制标准，一个是DCF(分布式协调功能)，没有中心控制站，使用CSMA/CA争用信道获取发送权，802.11的默认方式；另一个是PCF(点协调功能)，使用集中控制的接入算法（一般在接入点AP实现集中控制），实际中较少使用</p></li> <li><p>IFS帧间间隔，站点必须在检测到信道空闲一段指定的时间间隔才能发送帧</p></li> <li><p>SIFS短帧帧间间隔（28微秒），使用SIFS的帧类型有ACK,CTS,过长MAC帧分片后的数据帧，所有回答AP探询的帧和PCF接入方式中接入点AP发送的任何帧</p></li> <li><p>（CSMA的退避算法）</p> <p><img src="/assets/img/image-20201217002418198.73e3eab0.png" alt="image-20201217002418198"></p></li> <li><p>DIFS(DCF帧间间隔)，在DCF中用来发送数据帧和管理帧</p></li> <li><p>CSMA/CA 高优先级的帧需要等待时间短，可以优先获得发送权</p></li> <li><p>csma/ca 源站点A给目的站点B发送RTS帧预约信道，目的站点B广播CTS帧说明允许A占用信道并说明占用的持续时间，其他站点收到该帧后延迟发送，A收到该帧后发送数据，每发送一个帧都要等待确认（因为无线通信的质量不如有线，所以需要停止等待协议），从而解决了隐蔽站问题</p></li> <li><p>出现网络拥塞时，路由器给源主机发送源点抑制ICMP报文，目的是告诉主机再发送就会丢弃数据报了，警告源主机放慢发送速度。路由器会持续发送源点抑制报文直到不再拥塞</p></li> <li><p>路由表中全0地址是默认路由，如果PDU不匹配默认路由之外的路由项，则转发给默认路由的下一跳地址</p></li> <li><p>给路由器配置默认路由是手动在路由表添加一个网络段和下一跳地址</p></li> <li><p>FAT既可以用于文件分配又可以用于空闲磁盘块的管理</p></li> <li><p>如果发送PDU的目的IP与本机IP不在同一个网段，则需要把PDU交给默认网关（默认路由）</p></li> <li><p>执行系统调用的过程：传递系统调用参数 -&gt; 执行trap指令 -&gt; 执行相应的服务程序 -&gt; 返回用户态</p></li> <li><p>操作系统不一定需要提供系统调用，但一定要有中断处理功能</p></li> <li><p>处理外部中断，应由操作系统保存的是通用寄存器而非PC， PC值由中断隐指令<em>自动保存</em></p></li> <li><p>进入中断处理的程序一定是<em>操作系统程序</em>，而不是用户程序</p></li> <li><p>分时系统追求的是比较快速响应用户</p></li> <li><p>文件存储空间管理就是文件空闲空间管理</p></li> <li><p>问启动了磁盘多少次时，求的是读的次数+写的次数，注意修改记录需要一次写回操作</p></li> <li><p>碰撞域：发送任意一个非多播地址的PDU，能够接受到该PDU的设备是碰撞域的一部分</p></li> <li><p>交换机能够隔离碰撞域（第一次接入拓扑时，由于ARP缓存为空，所以第一次收到PDU会进行一次多播，更新ARP后隔离碰撞域）</p></li> <li><p>频带范围最大值减去最小值就是香农定理需要的带宽W</p></li> <li><p>边是顶点的无序对，记为(v,w)或(w,v)</p> <p>弧是顶点的有序对,记为&lt;v.w&gt;,v称为弧尾,w称为弧头(名称有点反直觉，注意区分）</p></li> <li><p>平衡二叉树默认是二叉排序树</p></li> <li><p>Dijkstra算法的时间复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>V</mi><msup><mi mathvariant="normal">∣</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|V|^2)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord"><span class="mord mathrm">∣</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>，不允许负权值</p></li> <li><p>Floyd算法通过迭代更新经过第i个顶点的距离矩阵求任意两点的最短路径， 时间复杂度为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>V</mi><msup><mi mathvariant="normal">∣</mi><mn>3</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|V|^3)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord"><span class="mord mathrm">∣</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">3</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>,允许负权值的边，不允许负圈</p></li> <li><p>折半查找判定树的树高为 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>⌈</mo><mi>log</mi><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>⌉</mo></mrow><annotation encoding="application/x-tex">\lceil \log (n+1)\rceil</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">⌈</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mbin">+</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mclose">⌉</span></span></span></span></p></li> <li><p>活动的最晚开始时间=min{整个工期的时间-活动开始节点到终点的路径时间}</p></li> <li><p>当边的权值不唯一时，图的最小生成树唯一</p></li> <li><p>顺序查找（默认指链表的顺序查找），无序查找失败的平均查找长度是 n+1（比较n个元素失败，加上一次比较是否到达尾部），有序查找失败的平均查找长度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mfrac><mrow><mi>n</mi></mrow><mrow><mn>2</mn></mrow></mfrac></mrow><annotation encoding="application/x-tex">\frac{n}{2}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.695392em;"></span><span class="strut bottom" style="height:1.040392em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">2</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit">n</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span></span></span></span></p></li> <li><p>Prim算法时间复杂度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>V</mi><msup><mi mathvariant="normal">∣</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|V|^2)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord"><span class="mord mathrm">∣</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>, Kruskal算法的时间复杂度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>E</mi><mi mathvariant="normal">∣</mi><mi>log</mi><mi mathvariant="normal">∣</mi><mi>E</mi><mi mathvariant="normal">∣</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|E|\log |E|)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.05764em;">E</span><span class="mord mathrm">∣</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.05764em;">E</span><span class="mord mathrm">∣</span><span class="mclose">)</span></span></span></span></p></li> <li><p>BFS和DFS，邻接矩阵的时间复杂度 = <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>V</mi><msup><mi mathvariant="normal">∣</mi><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|V|^2)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord"><span class="mord mathrm">∣</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span>,邻接表的时间复杂度= <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>V</mi><mi mathvariant="normal">∣</mi><mo>+</mo><mi mathvariant="normal">∣</mi><mi>E</mi><mi mathvariant="normal">∣</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|V| + |E|)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathrm">∣</span><span class="mbin">+</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.05764em;">E</span><span class="mord mathrm">∣</span><span class="mclose">)</span></span></span></span>，空间复杂度都是  <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi mathvariant="normal">∣</mi><mi>V</mi><mi mathvariant="normal">∣</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(|V|)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathrm">∣</span><span class="mclose">)</span></span></span></span></p></li> <li><p>任意两个顶点都是连通的无向图称为连通图，无向图的极大连通子图称为连通分量</p></li> <li><p>任意两个顶点<em>相互</em>都有路径的有向图称为强连通图，有向图的极大强连通子图称为强连通分量</p></li> <li><p>线索二叉树的遍历，唯独后续遍历线索树仍需要栈的支持</p></li> <li><p>顶点序列第一个顶点和最后一个顶点相同的路径称为环或回路，除了首尾顶点，其余顶点不重复出现的回路称为简单回路</p></li> <li><p>一般图G满足 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi mathvariant="normal">∣</mi><mi>E</mi><mi mathvariant="normal">∣</mi><mo>≤</mo><mi mathvariant="normal">∣</mi><mi>V</mi><mi mathvariant="normal">∣</mi><mi>log</mi><mi mathvariant="normal">∣</mi><mi>V</mi><mi mathvariant="normal">∣</mi></mrow><annotation encoding="application/x-tex">|E| \le |V|\log |V|</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.05764em;">E</span><span class="mord mathrm">∣</span><span class="mrel">≤</span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathrm">∣</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mord mathrm">∣</span><span class="mord mathit" style="margin-right:0.22222em;">V</span><span class="mord mathrm">∣</span></span></span></span>时，将G视为稀疏图，反之为稠密图</p></li> <li><p>有向完全图任意两个顶点<em>相互</em>都有<em>弧</em></p></li> <li><p>图G的顶点集V和边集E的子集V’,E’不一定构成子图，因为E'关联的顶点不一定都在V'中</p></li> <li><p>连通图中生成树是图的包含<em>全部顶点</em>的<em>极小</em>（边数最少）连通子图</p></li> <li><p>非连通图中，每个连通分量的生成树构成了图的<em>生成森林</em></p></li> <li><p>广义指令只能在核心态下执行</p></li> <li><p>边界对齐：1.每个成员存储的起始地址％该成员的长度=0：2.结</p> <p>构体的长度必须为最大成员长度的整数倍。</p></li> <li><p>对于输入序列 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1,2,\cdots, n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">n</span></span></span></span>, 输入受限的双端队列得到的输出序列的特点：从每次从<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1,2,\cdots, n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">n</span></span></span></span>两边取一个追加到输出队列中；输出受限的双端队列的输出序列的特点：从1开始，每次在输出序列任意一侧添加下一个元素</p></li> <li><p>虚电路交换当发送方(或接收方)通知网络层它想终止该虚电路时才拆除虚电路</p></li> <li><p>用户态到核心态的转换是由<em>硬件</em>而非中断处理程序完成的</p></li> <li><p>机器字长指一次定点整数运算所能处理的二进制数据的位数</p></li> <li><p>int转float可能有数据舍入，转换成double可以保留精度；从float或double转成int，或从double换成float，可能溢出</p></li> <li><p>n个节点的完全二叉树的高度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>⌈</mo><mi>log</mi><mo>(</mo><mi>n</mi><mo>+</mo><mn>1</mn><mo>)</mo><mo>⌉</mo></mrow><annotation encoding="application/x-tex">\lceil \log (n + 1)\rceil</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">⌈</span><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mbin">+</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mclose">⌉</span></span></span></span></p></li> <li><p>操作系统提供给应用程序或用户的接口是函数调用，永远不要选库函数</p></li> <li><p>操作系统与用户的通信接口不包括对用户透明的管理，如缓存管理</p></li> <li><p>NRZ非归零编码：高低电平；NRZI反向非归零编码：翻转表示0，不翻转表示1</p></li> <li><p>信元交换就是虚电路分组交换</p></li> <li><p>SRAM是非破坏性读出，工作原理是触发器，不需要刷新，速度快，功耗大；DRAM是破坏性读出，利用电容存储电荷原理，需要定期刷新，逐行刷新</p></li> <li><p>尽管题干有给出信噪比，是否使用香农定理取决于问的是数据速率还是信道传输速率</p></li> <li><p>分组交换包括数据报交换和虚电路交换，数据报交换将数据封装成多个分组，独立转发</p></li> <li><p>脉冲编码调制PCM,将模拟信号转成数字信号；QAM正交振幅调制，将数字信号转成模拟信号</p></li> <li><p>利用模拟通信信道传输数字信号的方法称为频带传输</p></li> <li><p>利用脉冲信号传输数值信号的方法称为基带传输</p></li> <li><p>以太网帧最小长度64B</p></li> <li><p>Flash 存储器（FLASH EEPROM）按扇区进行操作，不属于随机存储器</p></li> <li><p>高响应比优先调度 的响应比 = \frac{周转时间}{服务时间}</p></li> <li><p>多重中断的屏蔽触发器的1的个数越多，说明优先级越高</p></li> <li><p>按序流动的流水线只可能出现RAW写后读相关</p></li> <li><p>IEEE754指数全0表示无穷小即0，全1表示正无穷或负无穷</p></li> <li><p>交叉多体并行存储器采用流水线的方式进行存取，连续读取m个字的时间是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>T</mi><mo>+</mo><mo>(</mo><mi>m</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>∗</mo><mi>r</mi></mrow><annotation encoding="application/x-tex">T + (m - 1)* r</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.13889em;">T</span><span class="mbin">+</span><span class="mopen">(</span><span class="mord mathit">m</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mbin">∗</span><span class="mord mathit" style="margin-right:0.02778em;">r</span></span></span></span>, T是读取一个字的存取周期，r是总线周期，m是交叉存取度，为了保证流水线不间断，应保证m <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>≥</mo></mrow><annotation encoding="application/x-tex">\ge</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.63597em;"></span><span class="strut bottom" style="height:0.7719400000000001em;vertical-align:-0.13597em;"></span><span class="base textstyle uncramped"><span class="mrel">≥</span></span></span></span> T / r</p></li> <li><p>cache访问效率e = cache访问时间 / 平均访问时间</p></li> <li><p>在进行模拟/数字信号的转换过程中，当<a href="https://baike.baidu.com/item/%E9%87%87%E6%A0%B7%E9%A2%91%E7%8E%87" target="_blank" rel="noopener noreferrer">采样频率<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>fs.max大于信号中最高频率fmax的2倍时(fs.max&gt;2fmax)，采样之后的数字信号完整地保留了原始信号中的信息，一般实际应用中保证采样频率为信号最高频率的2.56～4倍；采样定理又称<a href="https://baike.baidu.com/item/%E5%A5%88%E5%A5%8E%E6%96%AF%E7%89%B9%E5%AE%9A%E7%90%86" target="_blank" rel="noopener noreferrer">奈奎斯特定理<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a>。 [1]</p></li> <li><p>缺页中断作为中断同样要经历，诸如保护CPU环境、分析中断原因、转入缺页中断处理程序、恢复CPU环境等几个步驟·但与一般的中断相比，它有以下两个明显的区别：</p> <p>在指令执行期间产生和处理中断信号，而非一条指令执行完后。</p> <p>一条指令在执行期间，可能产生多次缺页中断</p></li> <li><p>子程序调用不需要保护PSW</p></li> <li><p>如果有向图的基图是连通图，则称有向图为弱连通图；如果有向图任意两个顶点vi，vj，</p></li> <li><p>n个顶点的图称为n阶图</p></li> <li><p>空图是顶点集为空的图，是特地规定的，严格说空图不是图，图的定义图的顶点集一定是非空集</p></li> <li><p>总线仲裁中，定时器轮询方式，当地址线的计数值与请求使用总线设备的地址一致时，该设备获得总线使用权，需要多组设备地址线</p></li> <li><p>数据字长是数据总线一次能并行传送信息的位数， <em>不</em>一定等于MDR的位数</p></li> <li><p>频繁的页面调度的现象称为抖动</p></li> <li><p>决定计算机计算精度的主要技术是机器字长</p></li> <li><p>计算机的运算速度值标的含义是每秒能执行多少个指令，不是指多少个操作系统的命令</p></li> <li><p>集成运算器和控制器的部件称为CPU，不是单片机；单片机具有完整的冯诺依曼结构：由运算器，控制器，存储器，输入输出设备等构成</p></li> <li><p>使用CSMA/CD协议时，最短帧长=发送速率*RTT</p></li> <li><p>电磁波在1km电缆的传播时延约为5 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>μ</mi><mi>s</mi></mrow><annotation encoding="application/x-tex">\mu s</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.43056em;"></span><span class="strut bottom" style="height:0.625em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathit">μ</span><span class="mord mathit">s</span></span></span></span></p></li> <li><p>十字链表只能用于有向图，边节点（i, j）同时在以i为首的出邻接表和以j为首的入邻接表中，数组第i个元素有两个指针分别指向以i为首的出邻接表和入邻接表</p></li> <li><p>邻接多重表只能用于无向图，特点是边节点数目等于边数， 边（i, j）的节点同时在以i为首和以j为首的邻接链表中，数组第i个元素存储的是与第i个节点邻接的边节点链表，一个边节点可能是多个链表的元素，故称邻接多重表</p></li> <li><p><img src="/assets/img/image-20201121170110074.4cbee65a.png" alt=""></p></li> <li><p>引起系统抖动的原因是对换的信息量过大、内存容量不足、置换算法选择不当，所以解决的办法就是降低交换页面的数量、加大内存容量、改变置换选择算法。但是降低交换页面数量和改变置换选择算法对于一个应用系统来讲是不可能的，只能增加内存容量，或者降低进程数量（相对地增加内存）。而增加交换区容量并不能解决物理内存不足的问题。</p></li> <li><p>改进的CLOCK算法如下：</p> <ol><li>从指针的当前位置开始循环扫描，直到找到使用位=0，修改位=0的帧并替换它</li> <li>如果查找失败，再扫描一次，直到找到使用位=0，修改位=1的帧并替换它，途中经过的帧使用位全部修改为1</li> <li>如果查找失败，再扫描一次，接下来必能在1和2中命中</li></ol></li> <li><p><img src="/assets/img/image-20201116103515881.88859b7f.png" alt="image-20201116103515881"></p></li> <li><p>信号量的C语言定义</p> <div class="language-c extra-class"><pre class="language-c"><code><span class="token keyword">typedef</span> <span class="token keyword">struct</span><span class="token punctuation">{</span>
    <span class="token keyword">int</span> value<span class="token punctuation">;</span> <span class="token comment">// 表示资源数量</span>
    <span class="token keyword">struct</span> <span class="token class-name">process</span> <span class="token operator">*</span> L<span class="token punctuation">;</span><span class="token comment">// 链接等待该资源的进程</span>
<span class="token punctuation">}</span> semaphore<span class="token punctuation">;</span>
</code></pre></div></li> <li><p>皮特森算法如下</p> <ol><li><img src="/assets/img/image-20201116102703524.68db9346.png" alt="image-20201116102703524"></li></ol></li> <li><p>指令流水线：取指、译码、执行、存结果</p></li> <li><p><img src="/assets/img/image-20201116095704586.84a720ed.png" alt="image-20201116095704586"></p></li> <li><p>突发传输一个总线周期传输一个地址和一批地址连续的数据，而并行存取流水线是一个存取周期进行多个总线周期的操作</p></li> <li><p>USB总线（中文名：通用串行总线）和SATA总线（中文名：串行ATA），他们的名字决定了必须是串行总线</p></li> <li><p><img src="/assets/img/image-20201116093859311.b0af9a14.png" alt="image-20201116093859311"></p></li> <li><p>边界对齐：如果数据占n个字节，则该数据地址m（按字节寻址的情况下） 令数据的存放满足 <code>m % n == 0</code>，则称为边界对齐，对于不超过1个字长的数据，只需要一次访存即可取出数据；边界对齐导致了C语言的结构体长度必须是成员中最大的对齐值的整数倍（不够就以空字节填充），定义的成员数据类型不一致时，不同的声明顺序可能会导致不同的结构体size，因此建议结构体将小于等于半字长的成员数据放在一起</p></li> <li><p>构造m叉归并树，如果 u = (n - 1) % (m - 1) $\ne $ 0,则需添加的虚段数 为 <em><code>m - u - 1</code></em></p></li> <li><p>数据结构用ElemType表示数据类型</p></li> <li><p>顺序表用来表示其他逻辑结构不方便（比如树形结构），顺序表存储密度大（因为不需要存储指针）</p></li> <li><p>问顺序表的存取结构时，顺序存取和随机存取二选一时，优先选随机存取</p></li> <li><p>数据结构的线性表对外暴露的下标是从1开始而非从0开始</p></li> <li><p>需要排序时，考虑能否使用计数排序</p></li> <li><p>链式存储设计节点内的存储单元地址一定连续</p></li> <li><p>逻辑结构可以独立于存储结构，存储结构不能独立于逻辑结构</p></li> <li><p>一个算法应该是问题求解的描述</p></li> <li><p>时间复杂度，是指最坏情况下的估算算法执行时间的一个上界</p></li> <li><p>给出不同的程序，每个程序以各个任务时间片给出时，用甘特图来求解， 时间为横轴， 程序类别为纵轴，cpu、io等时间用不同线类型区分</p></li> <li><p>二叉树可以是空树，度为2的树至少有一个度为2的节点，所以不能是空树，因此至少有一个根节点<em>不是</em>它们的共同点</p></li> <li><p>批处理操作系统的用户脱机使用计算机，作业是成批处理的，系统内多道程序并发执行，交互能力差</p></li> <li><p>保护现场信息一般是指PSWR程序状态字寄存器和某些通用寄存器的内容</p></li> <li><p>DBMS（数据库管理系统）是系统软件</p></li> <li><p>题目给出一个并发进程A和B的程序代码，默认是有多个进程A和多个进程B并发运行</p></li> <li><p>兼容指的是软件<em>或</em>硬件的通用性，通常在同一系列的不同型号的计算机中存在</p></li> <li><p>数据通路的功能是实现CPU内部的<em>运算器和寄存器</em>及寄存器之间的数据交换， 优化数据通路结构，可以有效提高计算机系统的吞吐量，从面加快程序的执行，Il正确。计算机 程序需要先转化成机器指令序列才能最终得到执行，通过对程序进行编译优化可以得到史优的指 令序列，从而使得程序的执行时间也越短，111正确。</p></li> <li><p>速度提高x%，则时间减少 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>−</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mn>1</mn><mo>+</mo><mi>x</mi><mi mathvariant="normal">%</mi></mrow></mfrac></mrow><annotation encoding="application/x-tex">1 - \frac{1}{1+x\%}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.845108em;"></span><span class="strut bottom" style="height:1.2484389999999999em;vertical-align:-0.403331em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mbin">−</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">1</span><span class="mbin">+</span><span class="mord mathit">x</span><span class="mord mathrm">%</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span></span></span></span></p></li> <li><p>编译程序属于系统软件</p></li> <li><p>MAR,PC,IR都是CPU的组成部分</p></li> <li><p>银行家算法<em>不</em>会限制用户申请资源的顺序，限制申请资源的顺序属于死锁的预防，破坏死锁的循环等待条件</p></li> <li><p>计算机最小的时间单位是时钟周期，不是CPU周期，CPU周期又称机器周期，由多个时钟周期组成</p></li> <li><p>MIPS衡量标量机的性能，MFLOPS衡量向量机的性能</p></li> <li><p>指令集、计算机组织、系统结构会影响CPI，CPU主频不会影响CPI</p></li> <li><p><em>会计电算化</em>属于数据处理的应用，<em>不</em>是科学计算的应用</p></li> <li><p>决定计算机精度的主要技术是计算机的字长</p></li> <li><p>数据库系统包括数据库管理系统、数据库管理员和数据库，数据库管理系统属于系统软件，但<em>数据库系统不属于系统软件</em></p></li> <li><p>存在PC中的地址依旧是逻辑地址</p></li> <li><p>取数指令信息流程如下：</p> <ol><li>取指令 PC-&gt;MAR-&gt;M-&gt;DR-&gt;IR</li> <li>分析指令 OP(IR)-&gt;CU</li> <li>执行指令 Ad(IR)-&gt;MAR-&gt;M-&gt;DR-&gt;ACC</li></ol></li> <li><p>取指令：PC-&gt;MAR-&gt;M-&gt;DR-&gt;IR</p></li> <li><p>计算机系统层次：（上层对下层功能扩展，下层是实现上层的基础）</p> <div class="language-mermaid extra-class"><pre class="language-text"><code>graph TD
高级语言机器 --&gt; 汇编语言机器 --&gt; 操作系统机器 --&gt; 机器语言机器 --&gt; 微指令系统
</code></pre></div></li> <li><p>分析指令： OP(IR)-&gt;CU</p></li> <li><p>执行指令：Ad(IR)-&gt;MAR-&gt;M-&gt;MDR-&gt;ACC</p></li> <li><p>存储字长=MAR的位数，数据字长不一定等于MDR的位数</p></li> <li><p>中断处理流程</p> <div class="language-mermaid extra-class"><pre class="language-text"><code>graph TD
	1[关中断] --&gt; 保存断点 --&gt; 中断服务程序寻址 --&gt; 保护现场和屏蔽字 --&gt; 2[开中断] --&gt; 执行中断服务程序 --&gt; 3[关中断] --&gt; 恢复现场和屏蔽字 --&gt; 4[开中断] --&gt; 中断返回
	
</code></pre></div></li> <li><p>分时操作系统可以让多个用户同时使用计算机，人机交互性强，具有每个用户独立使用计算机的独占性、系统响应及时</p></li> <li><p>缺页中断的处理包括换页+内存存取</p></li> <li><p>程序设计无法形成屏蔽中断指令</p></li> <li><p>多级中断屏蔽字1的个数越多优先级越高</p></li> <li><p>如果是芯片是m x n位，内存按n位字长编址， 则地址空间为0到$2 ^ m - 1 $</p></li> <li><p>CPU执行时间= （指令条数*CPI）/主频</p></li> <li><p>描述存储容量和文件大小通常用2的n次幂，描述速率、频率通常用10的幂来表示</p></li> <li><p>MAR是存储器的一部分，但现代计算机MAR和Cache都是存在于CPU中的</p></li> <li><p>冯诺依曼机以运算器为中心，哈佛结构以<em>存储器</em>为中心（即IO操作尽可能绕过CPU）</p></li> <li><p>计算机以二进制方式表示的理由是：有物理器件的性能确定，而非信息处理方便</p></li> <li><p>中断发生后，进入中断处理的程序属于操作系统程序</p></li> <li><p>中断是操作系统必须要提供的功能，因为计算机的各种错误需要中断来处理，核心态和用户态的切换也需要中断</p></li> <li><p>计算机通过硬件来完成从用户态到核心态的转换</p></li> <li><p>解释程序不会将源程序翻译成机器语言，而是边解释边执行</p></li> <li><p>编译程序和解释程序的作用都是讲高级语言程序转换成<em>机器语言程序</em></p></li> <li><p>实时操作系统能够对控制对象作出及时反应，可靠性高，响应及时，但资源利用率低</p></li> <li><p>操作系统的最基本的特征是<em>并发和共享</em></p></li> <li><p>取数、读时钟、寄存器清0，不一定要在核心态下运行</p></li> <li><p>置时钟指令只能在核心态下运行</p></li> <li><p>部分软件（使用频繁，硬件代价不是很高）的功能可以用硬件取代</p></li> <li><p>通道是一种控制一台或多台外部设备的硬件机构，一旦启动就独立于CPU运行，为了让cpu了解通道工作已完成，需要引入中断</p></li> <li><p>缺页中断、非法操作码、算术溢出、地址越界都是内中断，IO中断和时钟中断（用于处理时间片）都是外中断</p></li> <li><p>CPU包括IR，通用寄存器和地址寄存器，但不包括地址译码器，地址译码器在存储器中</p></li> <li><p>电子计算机的发展的4代主要元件依次是电子管、晶体管、中小规模集成电路、大规模集成电路</p></li> <li><p>广义指令一定只能在核心态下执行</p></li> <li><p>软件和硬件具有逻辑上的等效性</p></li> <li><p>用户及应用程序和应用系统是通过系统调用提供的支持和服务来使用系统资源来完成其操作的</p></li> <li><p>顺序性多道程序设计的基本特征</p></li> <li><p>用户态只能使用非特权指令，核心态可以使用全部指令</p></li> <li><p>微内核结构将很多服务移动到内核之外（如文件系统），添加系统服务时不需要修改内核，服务之间使用进程间通信，因此影响了系统的效率；由于内核服务少，因此更稳定</p></li> <li><p>处理外中断，PC由中断隐指令保存，通用寄存器的内容有操作系统保存</p></li> <li><p>多任务操作系统的主要特点是并发和并行</p></li> <li><p>并发和共享是OS的最基本的特征，两者互为存在条件</p></li> <li><p>RTT蕴含了传播时延，传播时延等于RTT的一半</p></li> <li><p>I/O设备和CPU并行工作是借助于中断技术实现的</p></li> <li><p>每发送一个分组等待一个RTT才能发下一个,则发送n个分组需要等待(n-1)个RTT</p></li> <li><p>每等待一个RTT，可以发送m个分组，则发送n个分组需要（n/m-1)个RTT，因为最后一个分组不需要等待</p></li> <li><p>操作系统为编程人员和应用程序 提供的接口是程序接口，即系统调用</p></li> <li><p>广义指令是系统调用命令，命令解释器是命令接口，Shell就是命令解析器，缓存管理全部由操作系统管理，对用户是透明的，系统不提供缓存管理的系统调用</p></li> <li><p>电路交换不采用存储转发技术，电路交换总时延=发送时延+传播时延+连接时延，分组交换时延=发送时延+传播时延</p></li> <li><p>带宽单位是Hz或比特每秒(b/s)，不能是字节每秒(B/s)</p></li> <li><p>计算机网络分层的目的永远不包括定义功能执行的<em>方法</em>（即实现细节）</p></li> <li><p>可以实现让权等待的同步机制是 <strong>信号量方法</strong></p></li> <li><p>intranet内部网， internet互联网</p></li> <li><p>对于分组交换，设共有n个分组，经过k段链路，分组大小为p，由于采用存储转发技术，一个站点的发送时延为t=p/b。</p> <p>显然，数据在信道中经过k-1个／时间的流动后，从第k个t开始，每个t时间段内将有一个分</p> <p>组到达目的站，总发送时延 = np/b + (k-1)p/b</p></li> <li><p>在OSI模型中同时提供无连接服务和面向连接服务的是<em>网络层</em>而非传输层，这和TCP/IP模型是相反的</p></li> <li><p>OSI模型中通过在文件中插入同步点防止重传整个文件的层是会话层</p></li> <li><p>OSI模型中提供建立、维护、拆除端到端连接的连接的层是传输层而不是会话层</p></li> <li><p>链路层提供点对点通信， 传输层提供端对端通信</p></li> <li><p>异构网络指物理层和链路层不同</p></li> <li><p>路由器的每一个端口都要有一个ip地址</p></li> <li><p>猝发传输：在一个总线周期内传输多个地址连续的数据字</p></li> <li><p>NAT路由器涉及到了传输层</p></li> <li><p>FTP控制端口号是21，数据连接端口号是20，记忆：0数1控</p></li> <li><p>TCP有20B的固定首部，UDP只有8B</p></li> <li><p>二进制反码求和的先取反再相加和<em>先相加再取反</em>的结果是一样的</p></li> <li><p>关中断-&gt;<em>保存断点（保存地址）</em>-&gt;引出中断服务程序-&gt;<em>保存现场和屏蔽字</em>-&gt;开中断-&gt;执行中断服务程序-&gt;关中断-&gt;恢复现场和屏蔽字-&gt;开中断-&gt;中断返回</p></li> <li><p>DMA开始前通过程序预处理，结束后通过中断进行后处理</p></li> <li><p>TCP面向连接，保证顺序交付</p></li> <li><p>带权周转时间=<em>周转时间/运行时间</em></p></li> <li><p>使用CIDR时，使用最长前缀匹配</p></li> <li><p>远程登录需要保证可靠连接，因此不能使用UDP；UDP由于开销小，可用在客户/服务器，远程调用，多媒体应用</p></li> <li><p>ipv6固定首部，128bit地址，提供qos保障，减少了头部字段数目，取消了校验和，不允许分片</p></li> <li><p>ARP和RARP属于网络层</p></li> <li><p>DHCP是基于UDP的，因为不知道对方的ip地址，所以不可能通过套接字建立连接，所以只能多播和使用UDP</p></li> <li><p>nat转换表映射包括端口号《ip地址，端口号》</p></li> <li><p>ICMP属于网络层协议，ping使用icmp回送请求和回答报文，工作在应用层，但是未使用TCP和UDP，traceroute使用icmp时间超过报文，工作在网络层</p></li> <li><p>目的地址为环回地址的IP数据报永远不会出现在任何网络上</p></li> <li><p>模拟传输需要放大器放大信号；数字传输需要中继器将失真的信号整形</p></li> <li><p>单模光纤衰耗小， 适合远距离传输</p></li> <li><p>IP固定首部20B，首部最大长度60B，IP数据报最大长度65535B，如果超过以太网帧最大传送单元MTU的1500B或许多广域网的MTU的576B，则需要分片</p></li> <li><p>IP首部的DF=1表示不允许分片，MF=1表示后面还有分片，协议号=6表示TCP,=17表示UDP</p></li> <li><p>多模光纤容易失真，适合近距离传输</p></li> <li><p>流量窗口机制发送窗口取接收窗口rwnd和拥塞窗口cwnd的最小值</p></li> <li><p>无线电波用于手机通信，信号朝所有方向传播</p></li> <li><p>微波和红外线的信号向固定方向传播</p></li> <li><p>5-4-3规则是为了限制中继器使用次数的，
5是指不能超过5个网段
4是指在这些网段中的物理层网络设备（中继器，集线器）最多不超过4个
3是指这些网段中最多只有三个网段挂有计算机</p></li> <li><p>时延带宽积 （即以比特为单位的链路长度）= 传播时延*带宽</p></li> <li><p>中继器、集线器和网桥都不能抑制广播风暴，只有<em>路由器</em>能抑制广播风暴</p></li> <li><p>中继器用于放大信号，又称转发器Repeater</p></li> <li><p>递归解析另一个网络的域名是，主机和本地域名服务器发送的域名请求消息数都是1</p></li> <li><p>RIP协议提到收到的相邻路由器的距离向量是还没有被修改的</p></li> <li><p>跳数超过或等于16就不可达</p></li> <li><p>存储转发分组需要的时间（不考虑传播延迟和分组拆装时间）：发送时延+最后一个分组的传送时延</p></li> <li><p>单级中断系统的中断服务程序执行顺序是保护现场-&gt;中断时间处理-&gt;恢复现场-&gt;开中断-&gt;中断返回。注意关中断是在中断服务程序执行之前做的</p></li> <li><p>PCI,ISA,EISA,PCI-Express都是总线标准</p></li> <li><p><em>TLB</em>是translation lookaside buffer的简称（转译后备缓冲区),用于将虚拟地址转换成物理地址</p></li> <li><p>查找顺序是从TLB到页表到cache和主存，最后到外存</p></li> <li><p>单模光纤：如果光纤的直径减小到只有光的一个波长大小，那么光<em>沿直线传播</em></p></li> <li><p>放大器和中继器都起放大作用，只不过放大器放大的是模拟信号，原理是将衰减的信号放大，而中继器放大的是数字信号，原理是将衰减的信号整形再生</p></li> <li><p>操作系统频繁发生抖动的主要原因是频繁访问的页面数目大于可用的物理页帧数</p></li> <li><p>虚存容量=min{外存+内存，地址空间}</p></li> <li><p>保证顶点连通的最小边数是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>+</mo><mfrac><mrow><mo>(</mo><mi>n</mi><mo>−</mo><mn>1</mn><mo>)</mo><mo>(</mo><mi>n</mi><mo>−</mo><mn>2</mn><mo>)</mo></mrow><mrow><mn>2</mn></mrow></mfrac></mrow><annotation encoding="application/x-tex">1+ \frac{(n-1)(n-2)}{2}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:1.01em;"></span><span class="strut bottom" style="height:1.355em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mbin">+</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">2</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.485em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mopen">(</span><span class="mord mathit">n</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mbin">−</span><span class="mord mathrm">2</span><span class="mclose">)</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span></span></span></span></p></li> <li><p>程序计数器pc对汇编程序员来说是可见的，但MAR,MDR,IR却是不可见的</p></li> <li><p>条件转移、数据相关和资源冲突都会引起指令流水线阻塞，数据旁路转发不会引起指令流水阻塞</p></li> <li><p>透明传输有字符计数法、0比特填充法、字符填充法、违规编码法。字符计数法count字段有差错会导致灾难性后果，字符填充法实现复杂，不具有兼容性，目前普遍使用的是<em>比特填充法</em>和违规编码法</p></li> <li><p>停止等待协议：每发送一个帧就等待确认，等待时间超过超时重传时间（一般略大于平均RTT）就重传</p></li> <li><p>后退N帧协议（GBN） ，连续发送多个数据帧，收到确认帧，那它和它之前的数据帧都已收到；否则丢弃之后的帧并且重传</p></li> <li><p>选择重传协议（SR）：有发送窗口和接受窗口，只重传错误的帧</p></li> <li><p>双绞线分为屏蔽双绞线STP，非屏蔽双绞线UTP，双绞线价格便宜，普遍用于<em>局域网</em>和传统电话网，通信距离一般为几公里</p></li> <li><p>同轴电缆：传输距离比双绞线<em>远</em>，价格更贵。分成<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>5</mn><mn>0</mn><mi mathvariant="normal">Ω</mi></mrow><annotation encoding="application/x-tex">50\Omega</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">5</span><span class="mord mathrm">0</span><span class="mord mathrm">Ω</span></span></span></span>同轴电缆（用于局域网，也称基带同轴电缆）和 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>7</mn><mn>5</mn><mi mathvariant="normal">Ω</mi></mrow><annotation encoding="application/x-tex">75\Omega</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.68333em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">7</span><span class="mord mathrm">5</span><span class="mord mathrm">Ω</span></span></span></span>同轴电缆（用于有线电视，也称宽带同轴电缆）小电阻对应局域网，基带</p></li> <li><p>标准以太网10Mbps，快速以太网100Mbps，千兆1000Mbps，10G以太网，逻辑拓扑是总线型，物理拓扑是星型，使用CSMA/CD</p></li> <li><p>无线局域网：采用IEEE802.11标准,涉及链路层和物理层。数据链路层划分为逻辑链路子层(LLC)和介质访问控制子层（MAC)</p></li> <li><p>频分复用FDM</p></li> <li><p>一台主机对应多个域名：虚拟主机；一个域名对应多个主机：负载均衡；一个主机对应多个MAC或IP：双线接入（路由器）</p></li> <li><p>提供客户访问的主机一定要有IP地址，域名是可选的</p></li> <li><p>21端口（控制端口)</p></li> <li><p>FTP不适合在两个计算机之间共享读写文件</p></li> <li><p>FTP的21控制连接一直保持打开状态，数据连接用完就关闭</p></li> <li><p>时分复用TDM</p></li> <li><p>统计时分复用STDM</p></li> <li><p>ftp支持带外传送，带外数据即需要尽快通知对方的紧急数据，TCP有URG指针和URG标识，支持带外传送，ftp是使用tcp的，udp不支持带外传送</p></li> <li><p>FTP匿名访问使用anonymous标识</p></li> <li><p>ftp允许用户指定文件的类型和格式</p></li> <li><p>电子邮件系统包括用户代理，邮件服务器，电子邮件协议；用户代理(UA)即邮箱客户端程序，通过SMTP发送到邮件服务器A，邮件服务器A通过SMTP发送邮件到邮件服务器B，接收方使用POP3从B中读取邮件，POP3（邮局协议v3）有下载并保留和下载并删除两个工作模式</p></li> <li><p>电子邮件包括首部和主体，首部必填项：To字段和From字段；smtp只能发送ASCII文本，通过MIME（多用途网络邮件扩充）可以发送非ascii数据，增加邮件主体的结构，事实上MIME重新将数据编码成了ASCII文本</p></li> <li><p>POP使用明文传输</p></li> <li><p>目的邮件服务器不工作或网络中断或导致邮件发送失败</p></li> <li><p>SMTP接收方服务器等待连接的端口号是25</p></li> <li><p>POP3由客户端而非服务端选择接收后是否保留在服务器上，pop3协议登录到服务器后，发送的密码是明文，一个账号在服务器上只能有一个接受目录</p></li> <li><p>http连接connection字段为close说明是非持续连接，为keep-alive说明是持续连接</p></li> <li><p>SMTP使用25端口，POP3使用110端口，IMAP（网络报文存取协议）提供创建文件夹，在不同文件夹移动文件和查询邮件的功能，允许用户代理只获取报文的某些部分</p></li> <li><p>使用ftp读取服务器文件的过程：主机建立一个TCP连接到服务器上的21端口，发送登录账户和密码；服务返回登录成功信息后，主机随机打开一个端口，将端口号发送给服务器；主机发送读取文件命令，服务器使用20端口建立tcp连接到主机发送的端口号；主机发送完数据后关闭该数据连接</p></li> <li><p>浏览器与邮件服务器之间的接受、发送邮件使用http传送，邮件服务器之间继续使用smtp</p></li> <li><p>FTP服务器的20端口与客户机随即打开的端口连接，进行数据传输</p></li> <li><p>FTP使用两个连接使得FTP更简单，容易实现，并且方便在数据传输过程中发出终止传输等指令</p></li> <li><p>码分多路复用CDM</p></li> <li><p>顾客取号，销售叫号问题，不管有多少个销售人员，叫号都是按序逐个叫号的，不能同时有多个销售叫不同的号，因此这个同步问题中销售人员数只是一个干扰项</p></li> <li><p><strong>容量的K用1024来算， 数据传输速率的K用1000来算</strong></p></li> <li><p>磁盘的传输速率是用1000来算的</p></li> <li><p>文件控制块：用于描述和控制文件的数据结构</p></li> <li><p>纯ALOHA协议：想发就发，发送方在一定时间内收不到确认就判断为冲突，等待随机时间后重传</p></li> <li><p>时隙ALOHA协议：只能在时间片开始是发送，发生冲突必须等到下一个时间片开始时重传</p></li> <li><p>ieee754单精度浮点数的移码的真值是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>x</mi><mo>−</mo><mn>1</mn><mn>2</mn><mn>7</mn></mrow><annotation encoding="application/x-tex">x-127</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.72777em;vertical-align:-0.08333em;"></span><span class="base textstyle uncramped"><span class="mord mathit">x</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mord mathrm">2</span><span class="mord mathrm">7</span></span></span></span>，也就是说+0的移码是 0111 1111 ，而1000 0000表示的是+1；指数全0且尾数全为0时表示0，通过符号位区分正负0；指数为全1，尾数为全0表示inf，通过符号位区分正负；指数全为1，尾数不是全0，表示无效的数，即NaN</p></li> <li><p>flash memory闪存可以代替外部存储器，存储元有mos管组成，是半导体存储器，非易失性存储器，读写速度不一致</p></li> <li><p>有利于实现指令流水线的操作有:指令格式规整且长度一致，指令和数据按边界对齐存放，指令store、load指令才能对操作数进行访问</p></li> <li><p>如果不采用cache和指令预取技术，空操作的指令周期中寄存器的内容也可能改变，每个指令周期cpu都至少访问主存1次</p></li> <li><p>载波监听多路访问协议CSMA:检测到电压摆动值超过门限值，表明总线上至少有两个站同时在发送数据，，即发生了冲突，多个主机以多点接入的方式连接在一根总线上</p></li> <li><p>使用突发传输数据时，执行写任务需要写入地址，需要一个隐含的周期</p></li> <li><p>usb总线是串行传输的</p></li> <li><p>http的tcp三次握手在第三次握手时捎带http请求，因此请求和接受hmtl耗时一个RTT</p></li> <li><p><img src="/assets/img/image-20201003112242201.2e24d6e6.png" alt="image-20201003112242201"></p></li> <li><p>中断处理需要保存程序状态字寄存器，而子程序调用不需要</p></li> <li><p>虚拟存储只能基于非连续分配技术，不是只受外存容量的限制</p></li> <li><p>read系统调用的参数不包括文件名</p></li> <li><p>进程在处于临界区时能进行处理机调度，在系统调用完成并返回到用户态成能进行处理机调度</p></li> <li><p>直接为ICMP提供服务的协议是IP</p></li> <li><p>ip路由器的功能不包括确保传输的ip分组不丢失</p></li> <li><p>相应外部中断的过程中，中断隐指令完成的操作包括保存断点，关中断，形成中断服务程序入口地址并传送到pc</p></li> <li><p>边界对齐的要点简单来说，对于int型而言，起始地址为4的倍数；对于char类型而言，起始地址为任意字节皆可；对于short类型而言，起始地址为2的倍数</p></li> <li><p>截断二进制指数退避算法：基本退避时间为争用期 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>2</mn><mi>τ</mi></mrow><annotation encoding="application/x-tex">2\tau</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.64444em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">2</span><span class="mord mathit" style="margin-right:0.1132em;">τ</span></span></span></span>,最多重传16次，每次从 [0,1，\cdots, 2^{k-1}]中选一个随机数r，（k = min {重传次数， 10}）， 退避时间为 r倍的基本退避时间</p></li> <li><p>CSMA/CA载波监听多点接入/碰撞避免协议，用于无线局域网，有能量检测ED, 载波检测CS和能量载波混合检测三种检测信道空闲方式</p> <ol><li>空闲时发送RTS(request to send)帧：包括发射端的地址、接收端的地址、下一个数据将持续发送的时间；信道忙则等待</li> <li>接收端收到RTS后，发送CTS（clear to send)帧</li> <li>发送端收到CTS后，发送数据帧，并预约信道</li> <li>接收端用CRC检验，ok则发送ACK帧</li> <li>发送方收到ACK帧则发送下一帧，如果没有则采用二进制指数退避算法确随机推迟时间</li></ol></li> <li><p>mac地址：全球唯一的48位二进制地址，前24位由IEEE规定，后24位由厂家决定</p></li> <li><p>算法题出现了有序的条件，优先考虑对数复杂度的算法</p></li> <li><p>802.11帧：地址1-&gt;接收端，地址2-&gt;发送端， 地址3-&gt;目的地址， 地址4-&gt;源地址</p></li> <li><p>HDLC帧使用零比特填充，每5个1插入一个0</p></li> <li><p>NRU就是clock置换算法</p></li> <li><p>数据链路层有流量控制和差错检验功能</p></li> <li><p>10Mbps以太网的争用期是512比特时间，即<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>5</mn><mn>1</mn><mi mathvariant="normal">.</mi><mn>2</mn><mi>μ</mi><mi>s</mi></mrow><annotation encoding="application/x-tex">51.2\mu s</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">5</span><span class="mord mathrm">1</span><span class="mord mathrm">.</span><span class="mord mathrm">2</span><span class="mord mathit">μ</span><span class="mord mathit">s</span></span></span></span></p></li> <li><p>IEEE754浮点数隐含整数部分是1，不是0</p></li> <li><p>IEEE754单精度浮点数的阶码范围是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>(</mo><msup><mn>2</mn><mrow><mo>−</mo><mn>1</mn><mn>2</mn><mn>6</mn></mrow></msup><mo separator="true">,</mo><msup><mn>2</mn><mrow><mn>1</mn><mn>2</mn><mn>7</mn></mrow></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">(2^{-126},2^{127})</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:1.064108em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mopen">(</span><span class="mord"><span class="mord mathrm">2</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord">−</span><span class="mord mathrm">1</span><span class="mord mathrm">2</span><span class="mord mathrm">6</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mpunct">,</span><span class="mord"><span class="mord mathrm">2</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span><span class="mord mathrm">2</span><span class="mord mathrm">7</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span></p></li> <li><p>设备与设备控制器之间的接口是USB</p></li> <li><p>平均查询扇区的时间=1/2平均转一圈的时间</p></li> <li><p>中断I/O的数据传送由软件完成，DMA的数据传送由硬件完成</p></li> <li><p>为了实现CD快速随机播放，应使用连续结构</p></li> <li><p>银行家算法是避免死锁 的方法，与预防死锁不是一回事</p></li> <li><p>计算磁盘号、磁头号和扇区号的工作有设备驱动程序完成</p></li> <li><p>直通交换机转发一个以太网帧需要检查数据包的前14个字节，如果不包含前导码，则只需检测目的地址6B</p></li> <li><p>单个文件的长度与间接地址索引的级数有关，与索引结点的总数无关</p></li> <li><p>撤销部分进程可以缓解系统的抖动（系统的抖动是操作系统需要花费过多时间处理频繁的页面切换），但加大交换区的容量和提高用户进程的优先级对解决抖动无帮助</p></li> <li><p>CSMA/CA会对正确收到的数据帧进行确认，而CSMA/CD不能</p></li> <li><p><span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>L</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">L_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">L</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span> 中断屏蔽字的设置是：比 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>L</mi><mi>i</mi></msub></mrow><annotation encoding="application/x-tex">L_i</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">L</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathit">i</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>优先级高的置0，其余置1</p></li> <li><p>用户程序发出i/o请求后，系统的正确处理流程是用户程序-&gt;系统调用处理程序-&gt;设备驱动程序-&gt;中断处理程序</p></li> <li><p><img src="/assets/img/image-20200918141325282.1d994f03.png" alt="image-20200918141325282"></p></li> <li><p><img src="/assets/img/image-20200910104619464.b8b00df2.png" alt="image-20200910104619464"></p></li> <li><p><img src="/assets/img/image-20200910104635102.1e5d6d3f.png" alt="image-20200910104635102"></p></li> <li><p><img src="/assets/img/image-20200910105127837.2317236d.png" alt="image-20200910105127837"></p></li> <li><p>高级链路控制HDLC：所有帧都是用CRC校验，透明传输用0比特传输，采用全双工传输</p></li> <li><p>信道吞吐率=信道利用率*数据发送速率</p></li> <li><p>信道利用率 = \frac{数据帧长度}{数据发送速率\times 发送周期（即2倍的单向传播时延+数据发送时延）}（注意单位统一）</p></li> <li><blockquote><p><strong>曼彻斯特编码</strong>：单极性编码的缺点是没有办法区分此时是没有信号，还是有信号，但是信号是0.
这种编码方式是bit中间有信号，低-高跳转表示0，高-低跳转表示1，一个时钟周期只可以表示一个bit，并且必须通过两次采样才能得到一个bit。它能携带时钟信号，而且能区分此时是没有信号还是信号为0.</p> <p><strong>差分曼彻斯特编码</strong>：抗干扰能力比曼彻斯特编码更强。bit与bit之间有信号跳变，表示下一个bit为0，bit与bit之间没有信号跳变，表示下一个bit为1。</p></blockquote></li> <li><p>DNS传输层使用了 <strong>UDP</strong> 协议</p></li> <li><p>IEEE 802.1无线局域网的MAC协议CSMA/CA进行信道预约的方法是 <strong>交换RTS与CTS帧</strong></p></li> <li><p>数据报提供无连接服务，不同分组的传输路径可能不同</p></li> <li><p>虚电路方式提供连接服务，同一系列的分组传输路径相同，传输结束后拆除连接</p></li> <li><p>IP数据报有20B固定字节</p></li> <li><p><img src="/assets/img/image-20200910110334973.22b6bd29.png" alt="image-20200910110334973"></p></li> <li><p><strong>延迟写</strong> 可以提高文件访问速度</p></li> <li><p>给出数据传输率、单向传播时延、信道利用率，求数据帧长度的方法</p></li> <li><p><img src="/assets/img/image-20200910110746432.f25e570b.png" alt="image-20200910110746432"></p></li> <li><p><img src="/assets/img/image-20200910110949301.7851e3da.png" alt="image-20200910110949301"></p></li> <li><p>DHCP基于UDP</p></li> <li><p>ICMP网际控制报文协议 ping命令， traceroute</p></li> <li><p><img src="/assets/img/image-20200910111423841.e8d403b2.png" alt="image-20200910111423841"></p></li> <li><p>UDP找不到目的端口号，就丢弃报文，发送ICMP</p></li> <li><p>FTP使用TCP,21端口传请求，20端口传数据</p></li> <li><p>SMTP基于TCP,用于发送邮件</p></li> <li><p>POP3用于读取邮件，旧的POP3下载邮件后就在接受端邮件服务器中删除</p></li> <li><p>基于万维网的电子邮件：发送邮件和接受邮件都是用http协议</p></li> <li><p>封装IP分组的目的MAC地址是<strong>下一个路由器的</strong>MAC地址，不是IP分组最终要到达的主机的MAC地址</p></li> <li><p>SUB, AX, BX 如果AX小于BX,即计算结果符号位为1（假设没有溢出），则借位标志位CF=1</p></li> <li><p>某容量为256MB的存储器由若干个4M*8位的DRAM芯片构成，该DRAM芯片的地址引脚和数据引脚总数是19</p></li> <li><p>采用指令Cache和数据Cache分离的主要目的是减少指令流水线资源的冲突</p></li> <li><p>某计算机采用微程序控制器，共32条指令，公共的取指令微程序包含2条微指令，各指令对应的微程序平均有4个微指令组成，采用断定法（下地址字段法）确定下条微指令的地址，则微指令中下址字段的位数至少是8位</p></li> <li><p>一次总线事务中，主设备只需给出一个首地址，从设备就能从首地址开始的若干连续单元独处或写入多个数据，这种总线事务方式称为突发传输</p></li> <li><p>定时发出中断请求，用于IO的时间占整个CPU时间的占比至少是 \frac{处理时间}{中断请求间隔}</p></li> <li><p>加快虚实地址转换的是增大快表的容量和让页表常驻内存</p></li> <li><p>如果在交换机内的缓存里没有发送帧到目的地址的端口的记录，则使用广播的方式向所有的端口发送该帧</p></li> <li><p>散列表的成功时平均查找长度，计算所有<strong>需要查找</strong>的关键字的查找长度，求均值</p></li> <li><p>二叉树 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>n</mi><mn>0</mn></msub><mo>=</mo><msub><mi>n</mi><mn>2</mn></msub><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n_0 = n_2+1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.79444em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit">n</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mrel">=</span><span class="mord"><span class="mord mathit">n</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:0em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mbin">+</span><span class="mord mathrm">1</span></span></span></span></p></li> <li><p>上三角矩阵按行优先存储，数组下标为（从0开始）</p>
M_{i,j}= \begin{cases}
A[n\times (i-1)- \frac{(i-1)(i-2)}{2}+j-i]&amp;, j \ge i\\ 
M_{j,i}&amp;, 其他

\end{cases}

</li> <li><p>m阶B树，关键字个数为n， 高度为h，除了根节点，每个非叶子结点的子树个数在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>[</mo><mo>⌈</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>⌉</mo><mo separator="true">,</mo><mi>m</mi><mo>]</mo></mrow><annotation encoding="application/x-tex">[\lceil \frac{m}{2} \rceil, m]</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1.095em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mopen">[</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">2</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit">m</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌉</span><span class="mpunct">,</span><span class="mord mathit">m</span><span class="mclose">]</span></span></span></span>, 关键字个数在 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mo>[</mo><mo>⌈</mo><mfrac><mrow><mi>m</mi></mrow><mrow><mn>2</mn></mrow></mfrac><mo>⌉</mo><mo>−</mo><mn>1</mn><mo separator="true">,</mo><mi>m</mi><mo>−</mo><mn>1</mn><mo>]</mo></mrow><annotation encoding="application/x-tex">[\lceil \frac{m}{2} \rceil -1, m-1]</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1.095em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mopen">[</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathrm">2</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit">m</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌉</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathit">m</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">]</span></span></span></span>，故整个B树的最小关键字数是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo>+</mo><mn>2</mn><mo>(</mo><mo>⌈</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></mfrac><mo>⌉</mo><mo>−</mo><mn>1</mn><mo>)</mo><mo>+</mo><mn>2</mn><mo>⋅</mo><mo>⌈</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></mfrac><mo>⌉</mo><mo>⋅</mo><mo>(</mo><mo>⌈</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></mfrac><mo>⌉</mo><mo>−</mo><mn>1</mn><mo>)</mo><mo>+</mo><mn>2</mn><mo>⋅</mo><mo>⌈</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></mfrac><msup><mo>⌉</mo><mn>2</mn></msup><mo>⋅</mo><mo>(</mo><mo>⌈</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></mfrac><mo>⌉</mo><mo>−</mo><mn>1</mn><mo>)</mo><mo>=</mo><mn>1</mn><mo>+</mo><mn>2</mn><mo>⌈</mo><mfrac><mrow><mn>1</mn></mrow><mrow><mi>m</mi></mrow></mfrac><msup><mo>⌉</mo><mrow><mi>h</mi><mo>−</mo><mn>1</mn></mrow></msup></mrow><annotation encoding="application/x-tex">1+2(\lceil \frac{1}{m}\rceil-1)+2\cdot \lceil \frac{1}{m}\rceil \cdot (\lceil \frac{1}{m}\rceil-1)+2\cdot \lceil \frac{1}{m} \rceil^2 \cdot (\lceil \frac{1}{m}\rceil -1)= 1+ 2\lceil \frac{1}{m} \rceil ^{h-1}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.849108em;"></span><span class="strut bottom" style="height:1.194108em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mbin">+</span><span class="mord mathrm">2</span><span class="mopen">(</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌉</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mbin">+</span><span class="mord mathrm">2</span><span class="mbin">⋅</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌉</span><span class="mbin">⋅</span><span class="mopen">(</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌉</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mbin">+</span><span class="mord mathrm">2</span><span class="mbin">⋅</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose"><span class="mclose">⌉</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mbin">⋅</span><span class="mopen">(</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose">⌉</span><span class="mbin">−</span><span class="mord mathrm">1</span><span class="mclose">)</span><span class="mrel">=</span><span class="mord mathrm">1</span><span class="mbin">+</span><span class="mord mathrm">2</span><span class="mopen">⌈</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose"><span class="mclose">⌉</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit">h</span><span class="mbin">−</span><span class="mord mathrm">1</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span></p></li> <li><p>处理器与其他资源不一样，其他资源得不到满足进入阻塞态，处理器得不到满足进入就绪态</p></li> <li><p>单处理器系统，任何时刻都最多只有一个进程处于执行态（在死锁发生或cpu空闲时也可能没有进程进行）</p></li> <li><p>进程最大数目取决于内存大小</p></li> <li><p>只要就绪队列不为空，cpu就处于非空闲状态，效率不变；就绪数目的大小不会影响效率，cpu效率值cpu处于工作状态的时间比例，与平均周转时间无关</p></li> <li><p>在采用混合索引分配方式时，假如有<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>N</mi><mn>0</mn></msub></mrow><annotation encoding="application/x-tex">N_0</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.10903em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>个直接地址项，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>N</mi><mn>1</mn></msub></mrow><annotation encoding="application/x-tex">N_1</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.10903em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>个一次间接地址项，<span class="katex"><span class="katex-mathml"><math><semantics><mrow><msub><mi>N</mi><mn>2</mn></msub></mrow><annotation encoding="application/x-tex">N_2</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.68333em;"></span><span class="strut bottom" style="height:0.83333em;vertical-align:-0.15em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.10903em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span>个二次间址项，每个盘块的大小为M字节，盘块号占m个字节，所允许的文件最大长度是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>M</mi><mo>∗</mo><mo>(</mo><msub><mi>N</mi><mn>0</mn></msub><mo>+</mo><msub><mi>N</mi><mn>1</mn></msub><mo>⋅</mo><mfrac><mrow><mi>M</mi></mrow><mrow><mi>m</mi></mrow></mfrac><mo>+</mo><msub><mi>N</mi><mn>2</mn></msub><mo>⋅</mo><mo>(</mo><mfrac><mrow><mi>M</mi></mrow><mrow><mi>m</mi></mrow></mfrac><msup><mo>)</mo><mn>2</mn></msup><mo>)</mo></mrow><annotation encoding="application/x-tex">M*(N_0 + N_1 \cdot \frac{M}{m} + N_2 \cdot(\frac{M}{m})^2)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.872331em;"></span><span class="strut bottom" style="height:1.217331em;vertical-align:-0.345em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">M</span><span class="mbin">∗</span><span class="mopen">(</span><span class="mord"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.10903em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">0</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mbin">+</span><span class="mord"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.10903em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">1</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mbin">⋅</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">M</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mbin">+</span><span class="mord"><span class="mord mathit" style="margin-right:0.10903em;">N</span><span class="vlist"><span style="top:0.15em;margin-right:0.05em;margin-left:-0.10903em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mbin">⋅</span><span class="mopen">(</span><span class="mord reset-textstyle textstyle uncramped"><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span><span class="mfrac"><span class="vlist"><span style="top:0.345em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord scriptstyle cramped"><span class="mord mathit">m</span></span></span></span><span style="top:-0.22999999999999998em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle textstyle uncramped frac-line"></span></span><span style="top:-0.394em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathit" style="margin-right:0.10903em;">M</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="sizing reset-size5 size5 reset-textstyle textstyle uncramped nulldelimiter"></span></span><span class="mclose"><span class="mclose">)</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mclose">)</span></span></span></span></p></li> <li><p>设备分配是通过在系统中设置相应的数据结构实现的，不需要创建进程；启动程序会引起进程创建；用户登录成功，系统为其创建一个用户管理的进程，包括用户桌面、环境等，所有用户进程都会在该进程下创建和管理。</p></li> <li><p>引入线程可以提高程序并发执行的程度，减少程序执行的时空开销</p></li> <li><p>隐式链接分配每个文件维护一个盘块链表</p></li> <li><p>使用外设，先驱动后中断</p></li> <li><p>显示链接分配用到FAT，FAT存放所有盘块号的next指针，文件的FCB仅记录第一个盘块的盘块号，在FAT中查询该盘块可以找到属于此文件的盘块链</p></li> <li><p>处理速度慢的程序不能有效发挥并发的优势。键盘是低速设备，处理键盘输入不需要多线程</p></li> <li><p>用户级线程内核意识不到线程的存在</p></li> <li><p>合作进程可以用文件系统交换数据，因为管道就是一个特殊的文件；全局变量是针对同一个进程而言的，不同的进程有不同的变量，没有任何联系，因此不能用于交换数据</p></li> <li><p>进程优先级降低的合理时机可以是进程时间片用完的时候，而不是刚从就绪态进入运行态的时候</p></li> <li><p>管道不能同时双向数据传输，但不强调同时的话，说可以双向数据传输是对的</p></li> <li><p>管道的读操作和写操作都可能被阻塞，例如缓存区空或缓存区满的时候</p></li> <li><p>由于用户级线程和内核级线程的连接方式分为多对一、一对一、多对多，因此操作系统不一定为每个用户线程建立一个线程控制块</p></li> <li><p>判断二叉树是否为二分查找判定树的方法，根据中序序列给节点标上下标<span class="katex"><span class="katex-mathml"><math><semantics><mrow><mn>1</mn><mo separator="true">,</mo><mn>2</mn><mo separator="true">,</mo><mn>3</mn><mo separator="true">,</mo><mn>4</mn><mo separator="true">,</mo><mo>⋯</mo><mo separator="true">,</mo><mi>n</mi></mrow><annotation encoding="application/x-tex">1,2,3,4,\cdots, n</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.64444em;"></span><span class="strut bottom" style="height:0.8388800000000001em;vertical-align:-0.19444em;"></span><span class="base textstyle uncramped"><span class="mord mathrm">1</span><span class="mpunct">,</span><span class="mord mathrm">2</span><span class="mpunct">,</span><span class="mord mathrm">3</span><span class="mpunct">,</span><span class="mord mathrm">4</span><span class="mpunct">,</span><span class="minner">⋯</span><span class="mpunct">,</span><span class="mord mathit">n</span></span></span></span>,如果符合二分查找的过程，则为二分查找判定树，如果同时出现向上取整和向下取整，即矛盾，应排除</p></li> <li><p>主频等于单位时间的时钟周期数</p></li> <li><p>交叉编址</p></li> <li><p>时间局部性和空间局部性</p></li> <li><p>超标量流水线</p></li> <li><p>控制存储器</p></li> <li><p>文件系统的簇</p></li> <li><p>时钟中断做的事情</p></li> <li><p>多道程序系统的开销</p></li> <li><p>磁盘逻辑格式化程序做的工作是建立文件系统的根目录，对保存空闲磁盘块信息的数据结构进行初始化</p></li> <li><p>香农公式</p></li> <li><p>奈奎斯特定理（采样定理）</p></li> <li><p>FTP传送的控制命令使用的是建立在TCP之上的控制连接</p></li> <li><p>以太网交换机进行转发决策时使用的PDU地址是目的物理地址</p></li> <li><p>在osi模型中第一个自下而上提供端对端服务的层次是传输层</p></li> <li><p>软连接的引用计数不会增加</p></li> <li><p>系统调用打开io设备时，使用的设备标识是逻辑设备名</p></li> <li><p>地址长度是32位，段号占8位，则段长最大是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mn>2</mn><mrow><mn>2</mn><mn>4</mn></mrow></msup></mrow><annotation encoding="application/x-tex">2^{24}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.8141079999999999em;"></span><span class="strut bottom" style="height:0.8141079999999999em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathrm">2</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord mathrm">2</span><span class="mord mathrm">4</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span></p></li> <li><p>cache组号从0开始编号，组相联映射是组内全相联映射，组间直接映射；直接映射的行号=主存块号 mod cache行数，注意主存块号是从0开始编号；全相联映射是指主存可以映射到任意一行，cache地址结构包含完整的主存块号地址，实现复杂</p></li> <li><p>码元的传输速率单位是波特​Baud，简写为B，表示单位时间内信号波形的变换次数，也表示单位时间传输码元数，一个码元可能对应多个比特，单位是Hz</p></li> <li><p>不考虑热噪声影响，可用奈奎斯特公式(仅用于二进制数据)  计算理想低通信道的最高码元传输速率 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>C</mi><mo>=</mo><mn>2</mn><mi>W</mi><mo>⋅</mo><msub><mi>log</mi><mn>2</mn></msub><mi>N</mi></mrow><annotation encoding="application/x-tex">C=2W\cdot\log_2 N</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.69444em;"></span><span class="strut bottom" style="height:0.9388799999999999em;vertical-align:-0.24444em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.07153em;">C</span><span class="mrel">=</span><span class="mord mathrm">2</span><span class="mord mathit" style="margin-right:0.13889em;">W</span><span class="mbin">⋅</span><span class="mop"><span class="mop">lo<span style="margin-right:0.01389em;">g</span></span><span class="vlist"><span style="top:0.24444em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle cramped"><span class="mord mathrm">2</span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span><span class="mord mathit" style="margin-right:0.10903em;">N</span></span></span></span>,W是低通信道的带宽，N是物理状态数 ；考虑噪声，可用香农公式 极限传输速率 = 带宽 \log_2 (1 + 信噪比S/N)，带宽的单位是Hz</p></li> <li><p>CPU的主频=单位时间的时钟信号数</p></li> <li><p>IEEE802.11数据帧</p></li> <li><p>直接封装RIP， OSPF, BGP的协议分别是</p></li> <li><p>复习重点:问协议一般问封装该协议的下层协议是什么</p></li> <li><p>TCP的20端口与21端口的含义</p></li> <li><p>采用非递归方式重写递归程序不是必须要用栈</p></li> <li><p>函数调用的时候，必须要用栈保存必要的信息</p></li> <li><p>栈的入栈次序不能确定出栈次序</p></li> <li><p>内部排序选择归并排序而不是插入排序，可能的原因不包括归并排序程序代码更短</p></li> <li><p>二进制表示是有物理器件的性能（如1、0与高、低电平对应）决定的，不是由于信息处理方便</p></li> <li><p>汇编语言翻译成可执行程序的过程称为汇编，不是编译</p></li> <li><p>主存储器包括地址寄存器(MAR)、存储体、数据寄存器（MDR），虽然地址寄存器一般属于内存，但绝大多数现代计算机都集成到了CPU中，地址译码器是主存的构成成分，不属于CPU</p></li> <li><p>软件和硬件具有逻辑上的等效性，但不是等价的</p></li> <li><p>抽象数据类型（ADT）描述了数据的逻辑结构和抽象运算，通常用（数据对象，数据关系，
基本操作集）这样的三元组来表示，从而构成一个完整的数据结构定义。</p></li> <li><p>操作系统属于大型系统软件，编译程序属于语言处理程序，连接程序属于服务型程序，不属于应用软件</p></li> <li><p>相联存储器既可以按地址访问，也可以按内容访问</p></li> <li><p>冯.诺依曼机的工作方式是控制流驱动</p></li> <li><p>MIPS是指每秒执行多少百万条指令，即平均指令执行速度，用于衡量标量机的功能；MFLOPS是指每秒执行多少百万条浮点数运算，描述浮点数运算速度，用于衡量向量机的性能</p></li> <li><p>CPU主频指的是CPU的时钟频率</p></li> <li><p>CPI指的是平均一条指令使用的CPU时钟数</p></li> <li><p>MIPS = 主频/CPI (计算时主频的单位应化为MHz)</p></li> <li><p>浮点数的加减运算：对阶（小阶向大阶对齐，尾数右移n位，阶码+n），尾数求和，溢出判断（需要右规解决假溢出）规格化（左规直到符号位与最高位相异）、舍入（用恒置1或舍0取1法）</p></li> <li><p>平均指令周期 = 1/MIPS，单位为微秒</p></li> <li><p>寄存器之间的信息通路有 PC-&gt;MAR，Ad(IR)-&gt;MAR，MDR-&gt;X，MDR-&gt;IR,MDR-&gt;ACC,或ACC-&gt;MDR</p></li> <li><p>存储字长是指一个存储单元中的二进制代码的位数，等于MDR的位数，数据字长是指数据总线一次能并行传送信息的位数，可以与MDR不等</p></li> <li><p>TLB是快表</p></li> <li><p><img src="/assets/img/image-20201130173508710.47b8b379.png" alt="image-20201130173508710"></p></li> <li><p>数据结构包含数据对象、数据关系、基本操作集三个要素，缺一不可</p></li> <li><p>SCAN调度即电梯调度</p></li> <li><p>顺序存储结构是一种随机存取的结构</p></li> <li><p>算法原地工作是指辅助空间的个数是<em>常量</em>，不是说不需要任何额外的辅助空间</p></li> <li><p>程序不一定满足有穷性，如死循环，信息循环等；算法代表<em>问题求解步骤的描述</em></p></li> <li><p>pop3协议用户下载邮件后需要从服务器删除邮件，所以需要保证可靠传输，因此传输层使用TCP</p></li> <li><p>直接映射每次将一个主存块映射到一个cache块，采用回写方式，每个cache行需要增加一个修改位，直接映射的地址结构是[标记+块号+块内地址]，cache行的结构是[有效位+修改位（回写方式专用）+标记+块内容]</p></li> <li><p>机器字长是指机器一次能处理的位数；操作系统的位数是指可寻址的位数，与机器字长不同，一般情况下根据寄存器的位数判断机器字长</p></li> <li><p>IR,MDR,MAR是内部工作寄存器，对程序员不可见</p></li> <li><p>处理外部中断时，应该由操作系统保存的是通用寄存器的内容</p></li> <li><p>中断i/o方式，cpu与io端口交换的信息不可能是主存地址</p></li> <li><p>CSMA/CD是链路独享，不是共享，边发送数据帧，边检测是否发生冲突，信号传播延迟趋近0时，信道利用率接近100%</p></li> <li><p>迭代查询进行域名解析，发出的DNS查询次数最多是域名的级数，最少是0</p></li> <li><p>帧序号的比特数至少是2倍的滑动窗口大小</p></li> <li><p>如果路由表有多个目的地址匹配，则优先匹配网络前缀相同位数最长的</p></li> <li><p>吞吐率是指单位时间内处理请求的数量，是评价计算机系统性能的综合指标</p></li> <li><p>会计电算化属于计算机数据处理方面的应用</p></li> <li><p>以太网帧不包含前导码的话首部有18B</p></li> <li><p>后退N帧协议</p></li> <li><p>将高级语言源程序转换成机器级目标代码文件的程序是编译程序，转换成汇编语言的还是编译程序，解释程序直接执行程序，不会转换成目标代码，将汇编转成机器代码的是汇编程序</p></li> <li><p>中央处理器包括运算器和控制器</p></li> <li><p>单周期处理器的时钟频率较低，不能使用单总线结构数据通路，在指令执行过程中控制信号不变</p></li> <li><p>以太网规定最短帧长是64B，即512比特</p></li> <li><p>采用分离事务通信方式课可提高总线利用率</p></li> <li><p>主机可以访问默认网关所指向的路由器</p></li> <li><p>采用突发传输方式可以提高数据总线传输率</p></li> <li><p>SPOOLING技术需要外存和多道程序设计技术的支持，可以让多个作业共享一个独占设备，设备与输入输出井的数据传送不能由用户作业控制</p></li> <li><p>数据帧进入集线器后就会被广播到连在同一台集线器上的所有主机</p></li> <li><p>在请求分页式存储管理中，工作集的窗口大小为n，表明是在t时刻的工作集指的是在t时刻的<strong>前n个</strong>请求页面</p></li> <li><p>并行总线传输比串行总线传输速度快是错误的，还要看其他指标</p></li> <li><p>如果说中断是来自处理器外部的请求事件，DMA传送结束属于中断，而缺页和存储保护错不属于中断，而是异常（异常是指令执行过程中在处理器内部发生的事件）</p></li> <li><p>采用先变址后间址的寻址方式，操作数的有效地址是 ((I)+D), I是变址寄存器的编号，D是形式地址</p></li> <li><p>曼彻斯特编码向上跳变为0，向下跳变为1</p></li> <li><p>差分曼彻斯特编码左边界跳变为0，无跳变为1</p></li> <li><p>http请求报文的host表示浏览器曾浏览过host</p></li> <li><p>http请求使用无状态连接，不是持续连接</p></li> <li><p>散列表不利于顺序检索，顺序检索一般使用线性检索；为了加快检索速度，一般设立当前目录，从当前目录开始查找；顺序检索完成后返回逻辑地址</p></li> <li><p>流式结构是逻辑结构，连续文件和链接文件是物理结构，系统文件是按文件用途划分的</p></li> <li><p>索引文件由逻辑文件和索引表组成</p></li> <li><p>符号链接直接复制被链接文件的引用计数值，删除硬链接不影响符号链接</p></li> <li><p>不同进程打开同一个文件，各自维护自己的文件描述符和读写指针</p></li> <li><p>数据不再内存时，产生缺页中断，open操作需要文件路径名和文件名，read操作需要文件描述符（由open操作返回），缓存区首址，传送的字节数</p></li> <li><p>目录是FCB的集合</p></li> <li><p>顺序存取时顺序存取方式快；随机存取索引方式快</p></li> <li><p>索引结点存储文件描述信息，属于文件目录管理</p></li> <li><p>位示图 盘块号b = n(i-1)+j， 盘块号b、行号i、列号j都从1开始，行号i=(b-1)/n+1, 列号j=(b-1)%n+1</p></li> <li><p>索引表存放记录的逻辑地址而非物理地址</p></li> <li><p>修改记录，需要读+写，读操作寻址时需要IO，等待写回时已获得物理地址，不需要再寻址，仅需要写操作的一次IO</p></li> <li><p>FAT不仅记录了各个块的先后连接关系，同时还标记了空闲磁盘块；文件分配表的项与物理磁盘块一一对应，-1表示最后一块，-2（或-3，-4）表示磁盘空闲；可以使用FAT进行文件存储空间管理</p></li> <li><p>unix系统中，文件信息存放在索引结点中</p></li> <li><p>创建文件需要在目录中创建目录项，删除文件从目录中删除目录项，然后释放空间；打开文件将目录项从目录复制到打开文件表，返回文件描述符fd，后面的操作仅用fd而不是文件名进行</p></li> <li><p>读文件或写文件必须要先打开文件</p></li> <li><p>随意修改共享文件可能导致其他用户无文件可用或使用了不想用的文件，产生错误</p></li> <li><p>随意修改目录项可能导致非法使用文件和管理上的混乱</p></li> <li><p>为了防止随意修改文件和目录项，需要通过系统调用执行这些操作</p></li> <li><p>可以在目录下创建到其他目录文件的链接，硬链接和软连接都可以</p></li> <li><p>NRZ（非归零编码）最直观的编码，高电平表示1，低电平表示0</p></li> <li><p>NRZI(反向非归零编码)电平翻转表示0，不翻转为1</p></li> <li><p>以太网使用曼彻斯特编码</p></li> <li><p>cpu的运算速度除了看主频，还看cpu的架构、缓存、指令集、cpu的位数、cache大小等</p></li> <li><p>原码一位乘法，ACC乘积高位、MQ乘积低位，X被乘数，移位是逻辑右移</p></li> <li><p>存取控制矩阵用于用户访问保护</p></li> <li><p>顶点不重复出现的路径是简单路径；其余顶点不重复出现的回路是简单回路</p></li> <li><p>为了防止文件受损通常使用备份的方法</p></li> <li><p>邻接矩阵如果是非对称矩阵，则是有向图，一个顶点的度数和等于入度+出度，顶点i的度数等于i行的1的总数+i列的1的总数</p></li> <li><p>有向完全图是强连通有向图</p></li> <li><p>连通分量是极大连通子图</p></li> <li><p>无向连通图边最少就是一个树，有向连通图边最小就是一个环</p></li> <li><p>无向连通图如果是一个有向环，则每个顶点的度数为2</p></li> <li><p>任意两个顶点都有弧是完全图；任意两个顶点都有路径是连通图</p></li> <li><p>如果E的子集E’包含的顶点不全包含在V的子集V‘中，则E‘和V’无法构成子图</p></li> <li><p>补码一位乘法Booth算法被乘数是双符号位，乘数是单符号位且在最低位后面多了个辅助位，移位是算术右移</p></li> <li></li></ol> <div class="language- extra-class"><pre><code>  ![image-20200911093924331](个人-知识点总结.assets/image-20200911093924331.png)
</code></pre></div><ol start="172"><li><p>原码除法：恢复余数法，默认商1，如果错了，更改商并加回除数，移位是逻辑左移，最后如果余数是负数，需要恢复余数，并把低位商置0；不恢复余数法（加减交替法），最后一次需要恢复余数</p></li> <li><p>ip地址首部的源地址（4B）和目的地址（4B）分别在前20B的次末尾和末尾</p></li> <li><p>补码除法：加减交替法，双符号位；被除数和除数异号相加，同号相减；余数和除数同号商1，异号商0，商末位恒置1，而不是恢复余数，精度不超过 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><msup><mn>2</mn><mrow><mo>−</mo><mi>n</mi></mrow></msup></mrow><annotation encoding="application/x-tex">2^{-n}</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.771331em;"></span><span class="strut bottom" style="height:0.771331em;vertical-align:0em;"></span><span class="base textstyle uncramped"><span class="mord"><span class="mord mathrm">2</span><span class="vlist"><span style="top:-0.363em;margin-right:0.05em;"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span><span class="reset-textstyle scriptstyle uncramped"><span class="mord scriptstyle uncramped"><span class="mord">−</span><span class="mord mathit">n</span></span></span></span><span class="baseline-fix"><span class="fontsize-ensurer reset-size5 size5"><span style="font-size:0em;">​</span></span>​</span></span></span></span></span></span></p></li> <li><p>扇区是一次读写的最小数据量</p></li> <li><p>MAC帧数据范围46-1500B，帧长不足64B填充0字节（CSMA/CD算法的限制）</p></li> <li><p>做算法题涉及到查找，优先考虑O(1)时间复杂度的散列表而不是二分查找</p></li> <li><p>簇是文件分配的最小单位（dos系统）</p></li> <li><p>大端方式优先读入高字节，方便人类阅读；小端优先读入低字节，便于机器处理</p></li> <li><p>边界对齐的目的是为了每次读入一个变量不用多次访存</p></li> <li><p>互斥访问的方法：单标志位、双标志位先检查、双标志位后检查、peterson方法（靠谱）、中断屏蔽（内核态）、TestAndSet（简称TS指令或TSL，将检查和上锁合并成原子操作）</p></li> <li><p>让权等待：如果不能进入临界区，立即释放处理机，而不是忙则等待</p></li> <li><p>信号量机制：互斥S=1，P(S)，进入临界区 V(S);同步S=0,前驱进程末尾V(S),后驱进程开始P(S)</p></li> <li><p>实现互斥的P操作一定要放在实现同步的P操作之后，否则可能发生死锁；V操作不会导致进程阻塞，所以两个V操作的顺序可以交换</p></li> <li><p>多消费者-多生产者，如果缓冲区大小大于1，则必须设置专门的互斥信号量</p></li> <li><p>读者-写者问题：1个rw互斥信号量，一个count记录多少个读进程在访问文件，一个令P(rw)和检查count值的操作是原子操作的互斥信号量mutex</p></li> <li><p>字节单位从小到大依次为Byte、KB、MB、GB、TB、PB、EB、ZB、YB、DB、NB</p></li> <li><p>采用邻接表存储的BFS、DFS、分别是 <span class="katex"><span class="katex-mathml"><math><semantics><mrow><mi>O</mi><mo>(</mo><mi>n</mi><mo>∗</mo><mi>e</mi><mo>)</mo></mrow><annotation encoding="application/x-tex">O(n*e)</annotation></semantics></math></span><span aria-hidden="true" class="katex-html"><span class="strut" style="height:0.75em;"></span><span class="strut bottom" style="height:1em;vertical-align:-0.25em;"></span><span class="base textstyle uncramped"><span class="mord mathit" style="margin-right:0.02778em;">O</span><span class="mopen">(</span><span class="mord mathit">n</span><span class="mbin">∗</span><span class="mord mathit">e</span><span class="mclose">)</span></span></span></span></p></li> <li><p>扇区交替编号可以减少延迟时间</p></li> <li><p>SPOOLing技术</p></li> <li><p>死锁必要条件</p></li> <li><p>采用GBN的最大平均传输速率=发送窗口尺寸*数据帧长/RTT</p></li> <li><div class="language-c extra-class"><pre class="language-c"><code>semaphore rw <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
semaphore mutex <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> count <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
semaphore w <span class="token operator">=</span> <span class="token number">1</span><span class="token punctuation">;</span> <span class="token comment">// 用于实现写优先</span>

<span class="token function">writer</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">P</span><span class="token punctuation">(</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">P</span><span class="token punctuation">(</span>rw<span class="token punctuation">)</span><span class="token punctuation">;</span>
        写文件。。。
        <span class="token function">V</span><span class="token punctuation">(</span>rw<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">V</span><span class="token punctuation">(</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token function">reader</span><span class="token punctuation">(</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span><span class="token number">1</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">P</span><span class="token punctuation">(</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">P</span><span class="token punctuation">(</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token number">0</span> <span class="token operator">==</span> count<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token function">P</span><span class="token punctuation">(</span>rw<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token operator">++</span>count<span class="token punctuation">;</span>
		<span class="token function">V</span><span class="token punctuation">(</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token function">V</span><span class="token punctuation">(</span>w<span class="token punctuation">)</span><span class="token punctuation">;</span>
        读文件
        <span class="token function">P</span><span class="token punctuation">(</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token operator">--</span>count<span class="token punctuation">;</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token number">0</span> <span class="token operator">==</span> count<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            <span class="token function">V</span><span class="token punctuation">(</span>rw<span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token function">V</span><span class="token punctuation">(</span>mutex<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div></li> <li><p>用信号量实现互斥</p></li> <li><div class="language-c++ extra-class"><pre class="language-text"><code>int S = 1;
void wait(int S) {
  while (S&lt;= 0);// 此处有个不严谨的地方，wait方法是原子操作，那while等待将导致wait永远在等待，持续占用处理机资源。这个只是逻辑上的while，实际的操作不会永久占用处理机资源
  S=S-1;
}
void signal(int S) {
    S = S + 1;
}
</code></pre></div><div class="language-c extra-class"><pre class="language-c"><code><span class="token comment">/*记录型信号量的定义*/</span>
<span class="token keyword">typedef</span> <span class="token keyword">struct</span> <span class="token punctuation">{</span>
    <span class="token keyword">int</span> value<span class="token punctuation">;</span>
    <span class="token keyword">struct</span> <span class="token class-name">process</span> <span class="token operator">*</span>L<span class="token punctuation">;</span>
<span class="token punctuation">}</span> semaphore<span class="token punctuation">;</span>

<span class="token comment">/*某进程需要使用资源时，通过wait原语*/</span>
<span class="token keyword">void</span> <span class="token function">wait</span><span class="token punctuation">(</span>semaphore S<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    S<span class="token punctuation">.</span>value<span class="token operator">--</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>S<span class="token punctuation">.</span>value <span class="token operator">&lt;</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">block</span><span class="token punctuation">(</span>S<span class="token punctuation">.</span>L<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>

<span class="token keyword">void</span> <span class="token function">signal</span><span class="token punctuation">(</span>semaphore S<span class="token punctuation">)</span> <span class="token punctuation">{</span>
    s<span class="token punctuation">.</span>value<span class="token operator">++</span><span class="token punctuation">;</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>S<span class="token punctuation">.</span>value <span class="token operator">&lt;=</span> <span class="token number">0</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        <span class="token function">wakeup</span><span class="token punctuation">(</span>S<span class="token punctuation">.</span>L<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div></li></ol></div> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">Last Updated:</span> <span class="time">2021/2/11 下午10:55:23</span></div> <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh"><img alt="知识共享许可协议" src="" style="border-width:0"></a><br>本作品采用<a rel="license" href="http://creativecommons.org/licenses/by/4.0/">知识共享署名 4.0 国际许可协议</a>进行许可。

   
</footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/考研专区/2021考研政治总结.html" class="prev">
        2021考研政治总结
      </a></span> <span class="next"><a href="/考研专区/关键算法题解转载.html">
        关键算法题解转载
      </a>
      →
    </span></p></div>  <footer style="text-align:center;">备案号： 粤ICP备2021020303号</footer></main></div><div class="global-ui"><!----></div></div>
    <script src="/assets/js/app.c7d9ff18.js" defer></script><script src="/assets/js/2.cd56dec9.js" defer></script><script src="/assets/js/8.04726c3a.js" defer></script>
  </body>
</html>
